1
$\begingroup$

I learned this theorem in the graph theory textbook.

Theorem Every $2$-connected plane graph can be embedded in the plane so that any specified face is the exterior.

G=PlanarGraph[{1 <-> 2, 1 <-> 3, 1 <-> 4, 2 <-> 3, 3 <-> 4, 2 <-> 5, 5 <-> 6, 6 <-> 3}, VertexLabels -> All]

enter image description here

In the above embedding of this graph, we know $1256341$ is boundary of exterior face of $G$.

I don’t know if there is a way to make the triangle face $\Delta_{134}$ outside.

The above is just an example. For the graph $G$, maybe I can change the layout of some points by VertexCoordinates. But for the large number of vertices, I don’t know if there is a good and unified way to arbitrarily specify an external face and give a good plane drawing.

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ When the graph is 3-connected, IGLayoutTutte from my IGraph/M package can do this. (Your example graph is not 3-connected.) $\endgroup$ Commented Apr 10, 2021 at 15:17
  • $\begingroup$ @Szabolcs Thank you for your help. I think IGLayoutTutte is very good. I don’t know where is the difficulty of the not 3-connected. $\endgroup$ Commented Apr 10, 2021 at 15:28
  • 1
    $\begingroup$ The equations for the Tutte embedding are only guaranteed to be non-degenerate for 3-connected graphs. Mathematica's own Tutte layout (which BTW doesn't allow specifying the outer face) does not check if the graph is 3-connected. As a result, it outputs solutions where edges or vertices overlap with each other. $\endgroup$ Commented Apr 10, 2021 at 18:03
  • 1
    $\begingroup$ I believe it is possible to make use of the Tutte embeddig even for non-3-connnected graphs by first adding 'phantom edges' to them to make the 3-connected. It's not clear what the best way to do this would be. A naive way (certainly not the best) is to triangulate all faces except the outer face. I would like to implement something like this for IGraph/M in the future, but I haven't had time to do it yet. $\endgroup$ Commented Apr 10, 2021 at 18:06
  • 1
    $\begingroup$ You are right, it is far from trivial, which is why it's not done yet (my first few attempt a couple of years ago failed). IGraph/M is open source and contributions are always welcome. Not all contributions need to be code. If you want to spend some time to figure out how to best make an arbitrary planar graph 3-connected by adding extra edges, so that the Tutte layout can be applied effectively, that would be very useful. $\endgroup$ Commented Apr 11, 2021 at 7:00

1 Answer 1

Reset to default
1
$\begingroup$

To kick things off, I tried randomly moving the new interior into the chosen triangle (new exterior). If somebody came up with a function that could detect edge crossings, then this could run many times until a good configuration appeared - I doubt it would scale well for larger graphs, though it's a start:

(* Move the chosen points into the new exterior randomly *) exteriorChange[G_, ext_] := Module[{coords = GraphEmbedding[G], tri, newpoints}, tri = Polygon[coords[[ext]]]; newpoints = If[MemberQ[ext, #], coords[[#]], RandomPoint[tri]] & /@ VertexList[G]; Return[PlanarGraph[EdgeList[G], VertexCoordinates -> newpoints, VertexLabels -> "Name"]]] SeedRandom[53]; G = PlanarGraph[{1 <-> 2, 1 <-> 3, 1 <-> 4, 2 <-> 3, 3 <-> 4, 2 <-> 5, 5 <-> 6, 6 <-> 3}, VertexLabels -> All] Show[ Graphics[{EdgeForm[None], FaceForm[LightGray]}], exteriorChange[G, {1, 2, 3}] ]

planar graph

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you for your code, though it's just the beginning. $\endgroup$ Commented Apr 10, 2021 at 16:04

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.