Segment representation of a subclass of co-planar graphs

详细信息	查看全文 | 推荐本文 |

• 作者：Mathew C. Francis^a ; ^{francis@lirmm.fr} ; ^{mathewcfrancis@gmail.com} ; Jan Kratochví ; l^b ; ^{honza@kam.mff.cuni.cz} ; Tomá ; &scaron ; Vysko膷il^b ; ^{whisky@kam.mff.cuni.cz}
• 关键词：Geometric intersection graphs ; Segment graphs ; Co-planar graphs ; Partial 2-trees
• 刊名：Discrete Mathematics
• 出版年：2012
• 期刊代码：47_0012365x
• 类别：cp
• 出版时间：28 May, 2012
• 卷：312
• 期：10
• 页码：1815-1818
• 文件大小：217 K

摘要

A graph is a segment graph if its vertices can be mapped to line segments in the plane such that two vertices are adjacent if and only if their corresponding line segments intersect. Kratochv铆l and Kub臎na asked the question of whether the complements of planar graphs, called co-planar graphs, are segment graphs. We show here that the complements of all partial 2-trees are segment graphs.