5
$\begingroup$

Suppose that we have a non-planar graph $G$ which is undirected and connected. Our aim is to remove a set of edges and/or a set of vertices and convert make $G$ planar while keeping the connectedness.

Besides connectedness, $G$ is guaranteed to have enough connectivity so that removal of a reasonably small amount of vertices do not disconnect the graph and there are several paths between two specified vertices (removing one or two vertices do not let $G$ be a tree).

I have looked it up on the Internet and could not find any research. Maybe it is because I do not know the proper keywords.

Is there any research on this topic? If so, could you provide a reference?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Google for "maximum planar subgraph". $\endgroup$
    – adrianN
    Commented Jun 17, 2016 at 9:38
  • $\begingroup$ Is maintaining connectedness your only criterion? If so, any spanning tree is an answer to your question (every tree is planar) and there are well-known algorithms for computing those. $\endgroup$
    – David Richerby
    Commented Jun 17, 2016 at 9:54
  • $\begingroup$ @DavidRicherby That is a crucial point I failed to clarify in my question. Thank you for noticing. I am studying on disjoint paths problem in planar graphs. Therefore, finding a spanning tree would not help me. $\endgroup$
    – padawan
    Commented Jun 17, 2016 at 10:18

1 Answer 1

Reset to default
7
$\begingroup$

These problems usually appear under the name "X edge deletion" and "X vertex deletion", where X is the graph class of interest, e.g., X could be "planar". There are also different variants where you allow for say edge addition and deletion (these are "editing problems"), or the operation could be edge contraction and so on.

In other words, you seem to be interested in both planar vertex deletion and planar edge deletion. For starters, you can see [1] and [2] (the problems seem FPT parameterized by the number of operations $k$).

[1] Marx, Dániel, and Ildikó Schlotter. "Obtaining a planar graph by vertex deletion." Algorithmica 62.3-4 (2012): 807-822. -- Non-paywalled version here.

[2] Golovach, Petr A., Pim van’t Hof, and Daniël Paulusma. "Obtaining planarity by contracting few edges." Theoretical Computer Science 476 (2013): 38-46.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Thank you very much! These worth a lot to me right now. Actually, the phrase I was looking for is "Converting Apex graphs to planar with minimum number of vertex deletions." supposing that I have not misunderstood the term "apex graph" $\endgroup$
    – padawan
    Commented Jun 17, 2016 at 10:10
  • 1
    $\begingroup$ @cagirici Glad to be of help! A graph is an apex graph if you can turn it into a planar graph by deleting a single vertex (for $k$-apex graphs, you get the same result by removing $k$ vertices). There's a Wikipedia article on apex graphs that has information that could be of further help. $\endgroup$
    – Juho
    Commented Jun 17, 2016 at 10:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.