
Vertex splitting replaces a vertex by two copies and partitions its incident edges amongst the copies. This problem has been studied as a graph editing operation to achieve desired properties with as few splits as possible, most often planarity, for which the problem is NP-hard.Here we study how to minimize the number of splits to turn a plane graph into an outerplane one. We tackle this problem by establishing a direct connection between splitting a plane graph to outerplanarity, finding a connected face cover, and finding a feedback vertex set in its dual. We prove NP-completeness for plane biconnected graphs, while we show that a polynomial-time algorithm exists for maximal planar graphs. Additionally, we show upper and lower bounds for certain families of maximal planar graphs. Finally, we provide a SAT formulation for the problem, and evaluate it on a small benchmark.
Computational Geometry (cs.CG), FOS: Computer and information sciences, Extremal problems in graph theory, feedback vertex set, Planar graphs; geometric and topological aspects of graph theory, vertex splitting, Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.), Graph algorithms (graph-theoretic aspects), Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.), Computer Science - Computational Geometry, Structural characterization of families of graphs, outerplanarity
Computational Geometry (cs.CG), FOS: Computer and information sciences, Extremal problems in graph theory, feedback vertex set, Planar graphs; geometric and topological aspects of graph theory, vertex splitting, Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.), Graph algorithms (graph-theoretic aspects), Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.), Computer Science - Computational Geometry, Structural characterization of families of graphs, outerplanarity
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
