2026-07-25T05:52:09Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8267 2024-03-06T10:41:48Z ddc:004 open_access

Square-Contact Representations of Partial 2-Trees and Triconnected Simply-Nested Graphs Da Lozzo, Giordano Devanny, William E. Eppstein, David Johnson, Timothy Square-Contact Representations Partial 2-Trees Simply-Nested Graphs A square-contact representation of a planar graph G = (V,E) maps vertices in V to interior-disjoint axis-aligned squares in the plane and edges in E to adjacencies between the sides of the corresponding squares. In this paper, we study proper square-contact representations of planar graphs, in which any two squares are either disjoint or share infinitely many points. We characterize the partial 2-trees and the triconnected cycle-trees allowing for such representations. For partial 2-trees our characterization uses a simple forbidden subgraph whose structure forces a separating triangle in any embedding. For the triconnected cycle-trees, a subclass of the triconnected simply-nested graphs, we use a new structural decomposition for the graphs in this family, which may be of independent interest. Finally, we study square-contact representations of general triconnected simply-nested graphs with respect to their outerplanarity index. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Giordano Da Lozzo and William E. Devanny and David Eppstein and Timothy Johnson 2017 Is Part Of LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2017.24 urn:nbn:de:0030-drops-82675 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.24 eng https://creativecommons.org/licenses/by/3.0/legalcode