Abstrakt. Vi studerar kontakt representationer av kantviktade plana grafer, där hörn är rektanglar eller rektilinjära polygoner och kanter är polygonkontakter vars längder representerar kantvikterna. Vi visar att för varje given kant-viktad planar graf vars yttre yta är en fyrhörning, som är internt triangulerad och som inte har några separerande trianglar kan vi i linjär tid konstruera en kant-proportionalitet rektangulär dubbel om man finns och rapportera fel annars. För en given kombinatorisk struktur av kontakt representation och kant vikter tolkas som nedre gränser på kontaktlängderna, en motsvarande kontakt representation som minimerar storleken på omslutande rektangel kan hittas i linjär tid. Om den kombinatoriska strukturen inte är fast, visar vi NP-hårdhet att avgöra om en kontakt representation med avgränsade kontaktlängder finns. Slutligen ger vi en fullständig karakterisering av den rektlinjära polygon komplexitet som krävs för att representera bianslutna internt triangulerade grafer: För yttre plana grafer komplexitet 8 är tillräcklig och nödvändig, och för grafer med två intilliggande eller flera icke-adjacent inre hörn komplexiteten är obegränsad.
Nöllenburg et al. REF beakta rektangelrepresentationer av kantviktade grafer, där kantvikterna är proportionella mot längden på motsvarande kontakt.
Edge-weighted contact representations of planar graphs
{'venue': 'J. Graph Algorithms Appl.', 'journal': 'J. Graph Algorithms Appl.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}