Planar Graphs as VPG-Graphs
Autor: | Chaplick, Steven, Ueckerdt, Torsten, Didimo, W., Patrignani, M. |
---|---|
Jazyk: | angličtina |
Rok vydání: | 2012 |
Předmět: | |
Zdroj: | Graph Drawing. GD 2012, 174-186 STARTPAGE=174;ENDPAGE=186;TITLE=Graph Drawing. GD 2012 Graph Drawing ISBN: 9783642367625 Graph Drawing |
Popis: | A graph is b k -vpg when it has an intersection representation by paths in a rectangular grid with at most k bends (turns). It is known that all planar graphs are b 3-vpg and this was conjectured to be tight. We disprove this conjecture by showing that all planar graphs are b 2-vpg. We also show that the 4-connected planar graphs are a subclass of the intersection graphs of z-shapes (i.e., a special case of b 2-vpg). Additionally, we demonstrate that a b 2-vpg representation of a planar graph can be constructed in o(n 3/2) time. We further show that the triangle-free planar graphs are contact graphs of: l-shapes, γ-shapes, vertical segments, and horizontal segments (i.e., a special case of contact b 1-vpg). From this proof we gain a new proof that bipartite planar graphs are a subclass of 2-dir.keywordsplanar graphintersection graphvertical segmentouter facehorizontal segmentthese keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves. |
Databáze: | OpenAIRE |
Externí odkaz: |