1-String B₁-VPG Representations of Planar Partial 3-Trees and Some Subclasses

2015/06/24 by Biedl, Therese, Derka, Martin
#Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1506.07246

Abstract

Planar partial 3-trees are subgraphs of those planar graphs obtained by repeatedly inserting a vertex of degree 3 into a face. In this paper, we show that planar partial 3-trees have 1-string B₁-VPG representations, i.e., representations where every vertex is represented by an orthogonal curve with at most one bend, every two curves intersect at most once, and intersections of curves correspond to edges in the graph. We also that some subclasses of planar partial 3-trees have L-representations, i.e., a B₁-VPG representation where every curve has the shape of an L.

Related

• 1-String B₂-VPG Representation of Planar Graphs
• Order-preserving 1-string representations of planar graphs
• A note on planar partial 3-trees
• 4-connected planar graphs are in B₃-EPG
• B₀-VPG Representation of AT-free Outerplanar Graphs