On Plane Subgraphs of Complete Topological Drawings

Alfredo Garcia Olaverri, Alexander Pilz, Javier Tejel Altarriba

Abstract


Topological drawings are representations of graphs in the plane, where vertices are represented by points, and edges by simple curves connecting the points. A drawing is simple if two edges intersect at most in a single point, either at a common endpoint or at a proper crossing. In this paper we study properties of maximal plane subgraphs of simple drawings Dof the complete graph Kn on n vertices. Our main structural result is that maximal plane subgraphs are 2-connected and what we call essentially 3-edge-connected. Besides, any maximal plane subgraph contains at least 3n/2 edges. We also address the problem of obtaining a plane subgraph of Dn with the maximum number of edges, proving that this problem is NP-complete. However, given a plane spanning connected subgraph of Dn, a maximum plane augmentation of this subgraph can be found in O(n^3) time. As a side result, we also show that the problem of finding a largest compatible plane straight-line graph of two labeled point sets is NP-complete.


Keywords


graph; topological drawing; plane subgraph; NP-Complete problem.



ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications