Abstrakt. Kontaktdiagram över isotetiska rektanglar förenar många koncept från tillämpningar som VLSI och arkitektonisk design, beräkningsgeometri och GIS. Att minimera arean av deras motsvarande rektangulära layouter är ett nyckelproblem. Vi studerar området-optimering problem och visar att det är NP-hård att hitta en minsta area rektangulär layout av en given kontakt graf. Vi presenterar O(n)-tid algoritmer som konstruerar O(n 2 )-area rektangulära layouter för allmänna kontakt grafer och O(n log n)-area rektangulära layouter för träd. (För träd är detta en O(log n)-tillnärmningsalgoritm.) Vi presenterar också en oändlig familj av grafer (respektive träd) som kräver (n 2 ) (respektive, (n log n)) område. Vi härleder dessa resultat genom att presentera en ny karakterisering av grafer som tillåter rektangulära layouter, med hjälp av det relaterade begreppet rektangulära dualer. En följd av våra resultat relaterar den klass av grafer som tillåter rektangulära layouter till rektangel-of-influence ritningar.
Buchsbaum m.fl. REF ger en karakterisering av den klass av grafer som tillåter rektangulär kontakt graf representation.
Rectangular layouts and contact graphs
{'venue': 'TALG', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}