Skip to main content
added 4 characters in body
Source Link
Licheng Zhang
  • 1.9k
  • 6
  • 17

A graph is IC-planar if it admits a drawing in the plane with at most one crossing per edge and such that two pairs of crossing edges share no common end vertex. A graph $G$ is maximal in a graph class $G$ if no edge can be added to G without violating the defining class.

We can appropriately add edges to a triangulated graph so that the final graph becomes a maximal IC-planar graph. Therefore, constructing a 3-connected, 4-connected, and 5-connected maximal IC-planar graph is always achievable. 

My question is whether there exist maximal IC-planar graphs with cut vertices, whether there are maximal IC-planar graphs with connectivity 2, and whether there exist 6-connected maximal IC-planar graphs.

A graph is IC-planar if it admits a drawing in the plane with at most one crossing per edge and such that two pairs of crossing edges share no common end vertex. A graph $G$ is maximal in a graph class $G$ if no edge can be added to G without violating the defining class.

We can appropriately add edges to a triangulated graph so that the final graph becomes a maximal IC-planar graph. Therefore, constructing a 3-connected, 4-connected, and 5-connected maximal IC-planar graph is always achievable. My question is whether there exist IC-planar graphs with cut vertices, whether there are IC-planar graphs with connectivity 2, and whether there exist 6-connected IC-planar graphs.

A graph is IC-planar if it admits a drawing in the plane with at most one crossing per edge and such that two pairs of crossing edges share no common end vertex. A graph $G$ is maximal in a graph class $G$ if no edge can be added to G without violating the defining class.

We can appropriately add edges to a triangulated graph so that the final graph becomes a maximal IC-planar graph. Therefore, constructing a 3-connected, 4-connected, and 5-connected maximal IC-planar graph is always achievable. 

My question is whether there exist maximal IC-planar graphs with cut vertices, whether there are maximal IC-planar graphs with connectivity 2, and whether there exist 6-connected maximal IC-planar graphs.

Source Link
Licheng Zhang
  • 1.9k
  • 6
  • 17

What is the range of connectivity for maximal IC-planar graphs?

A graph is IC-planar if it admits a drawing in the plane with at most one crossing per edge and such that two pairs of crossing edges share no common end vertex. A graph $G$ is maximal in a graph class $G$ if no edge can be added to G without violating the defining class.

We can appropriately add edges to a triangulated graph so that the final graph becomes a maximal IC-planar graph. Therefore, constructing a 3-connected, 4-connected, and 5-connected maximal IC-planar graph is always achievable. My question is whether there exist IC-planar graphs with cut vertices, whether there are IC-planar graphs with connectivity 2, and whether there exist 6-connected IC-planar graphs.