3
$\begingroup$

Let $G$ be a plane graph. Let $G'$ be a supergraph of $G$ obtained by inserting a face vertex in each face of $G$ and connecting the face vertex to all vertices on the boundary of the face.

For example, let $G$ be the left graph of the following picture. $G'$ is on the right. We mark the newly added vertices and edges in pink. Does the resulting planar graph from above construction have a nice name like the dual graph?

enter image description here

$\endgroup$
3
  • 1
    $\begingroup$ It's analogous to barycentric subdivision. $\endgroup$
    – Ethan Bolker
    Sep 6, 2022 at 13:56
  • 1
    $\begingroup$ It seems related to Apollonian Networks: en.wikipedia.org/wiki/Apollonian_network $\endgroup$
    – dbal
    Sep 6, 2022 at 23:29
  • $\begingroup$ @dbal yes. When $G$ is a triangulation, $G’$ is an Apollonian. $\endgroup$
    – licheng
    Sep 7, 2022 at 0:16

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .