Intersection graphs of L-shapes and segments in the plane

详细信息    查看全文

• 作者：Stefan Felsner^a ; ^{felsner@math.tu-berlin.de" class="auth_mail" title="E-mail the corresponding author} ; Kolja Knauer^b ; ^{kolja.knauer@lif.univ-mrs.fr" class="auth_mail" title="E-mail the corresponding author} ; George B. Mertzios^c ; ^{george.mertzios@durham.ac.uk" class="auth_mail" title="E-mail the corresponding author} ; Torsten Ueckerdt^d ; ^{torsten.ueckerdt@kit.edu" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Intersection graphs ; Segment graphs ; Co-planar graphs ; kk-bend VPGVPG-graphs ; Planar 3-trees
• 刊名：Discrete Applied Mathematics
• 出版年：2016
• 出版时间：19 June 2016
• 年：2016
• 卷：206
• 期：Complete
• 页码：48-55
• 全文大小：478 K

文摘

An L-shape is the union of a horizontal and a vertical segment with a common endpoint. These come in four rotations: , ,$\text{<inline-figure baseline="0.0"><link id="lk000050" locator="fx2"></inline-figure>},\text{<inline-figure baseline="0.0"><link id="lk000055" locator="fx3"></inline-figure>}$ and $\text{<inline-figure baseline="0.0"><link id="lk000060" locator="fx4"></inline-figure>}$. A k$k$-bend path is a simple path in the plane, whose direction changes k$k$ times from horizontal to vertical. If a graph admits an intersection representation in which every vertex is represented by an , an or $\text{<inline-figure baseline="0.0"><link id="lk000075" locator="fx2"></inline-figure>}$, a k$k$-bend path, or a segment, then this graph is called an {}-graph, {,$\text{<inline-figure baseline="0.0"><link id="lk000090" locator="fx2"></inline-figure>}$}-graph, B_k$B_k$-VPG$VPG$-graph or SEG$SEG$-graph, respectively. Motivated by a theorem of Middendorf and Pfeiffer (1992), stating that every {,$\text{<inline-figure baseline="0.0"><link id="lk000100" locator="fx2"></inline-figure>}$}-graph is a SEG$SEG$-graph, we investigate several known subclasses of SEG$SEG$-graphs and show that they are {}-graphs, or B_k$B_k$-VPG$VPG$-graphs for some small constant k$k$. We show that all planar 3-trees, all line graphs of planar graphs, and all full subdivisions of planar graphs are {}-graphs. Furthermore we show that complements of planar graphs are B₁₇$B_{17}$-VPG$VPG$-graphs and complements of full subdivisions are B₂$B_2$-VPG$VPG$-graphs. Here a full subdivision is a graph in which each edge is subdivided at least once.