Name
Abstract | ||
|---|---|---|
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 O(nlogn) time. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1016/j.comgeo.2007.05.006 | Comput. Geom. |
Keywords | Field | DocType |
geometric graph,planar straight line graph,2-edge connected pslg,crossing-free red-blue,spanning tree,important special case,entire edge,k-1 edge,color,augmenting edge,adjacent vertex,different color,red-blue planar matching,connected component,line graph | Pseudoforest,Discrete mathematics,Combinatorics,Minimum degree spanning tree,Vertex (geometry),k-vertex-connected graph,Planar straight-line graph,Giant component,Connected component,Spanning tree,Mathematics | Journal |
Volume | Issue | ISSN |
39 | 1 | Computational Geometry: Theory and Applications |
Citations | PageRank | References |
9 | 0.63 | 10 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ferran Hurtado | 1 | 744 | 86.37 |
| Mikio Kano | 2 | 548 | 99.79 |
| David Rappaport | 3 | 75 | 8.34 |
| Csaba D. Tóth | 4 | 573 | 70.13 |