Encompassing colored planar straight line graphs
详细信息 查看全文
- 作者：Ferran Hurtado ; Mikio Kano ; David Rappaport ; Csaba D. Tó ; th
- 关键词：Geometric graph ; Spanning tree ; Color
- 刊名：Computational Geometry
- 出版年：2008
- 出版时间：January 2008
- 年：2008
- 卷：39
- 期：1
- 页码：14-23
- 全文大小：221 K
文摘
Consider a planar straight line graph (PSLG), G, with k connected components, k![]()
2. We show that if no component is a singleton, we can always find a vertex in one component that sees an entire edge in another component. This implies that when the vertices of G are colored, so that adjacent vertices have different colors, then (1) we can augment G with k−1 edges so that we get a color conforming connected PSLG; (2) if each component of G is 2-edge connected, then we can augment G with 2k−2 edges so that we get a 2-edge connected PSLG. Furthermore, we can determine a set of augmenting edges in O(nlogn) time. An important special case of this result is that any red–blue planar matching can be completed into a crossing-free red–blue spanning tree in 604397089be7d3d3d"" title=""Click to view the MathML source"">O(nlogn) time.