1
$\begingroup$

We say that a graph G is modular if for every three vertices x,y,z there exists a vertex w that lies on a shortest path between every two of x, y, z. Pseudo-modular (or "3-Helly") graphs are defined in the following link: http://www.graphclasses.org/classes/gc_203.html.

I am wondering if there are interesting examples of planar graphs which are modular or pseudo-modular, or an interesting characterization of planar graphs which have these properties.

$\endgroup$
2
$\begingroup$

The median graphs are a subclass of modular graphs with almost the same definition but where the vertex w is always unique. The squaregraphs (plane graphs in which all bounded faces are quadrilaterals and all vertices either have degree 4 or belong to the unbounded face) form a natural and interesting subclass of the planar median graphs. I believe that all planar median graphs can be constructed by gluing together cubes and squaregraphs, but I don't think this result has been published.

$\endgroup$
2
  • $\begingroup$ Thank you for your reply! I am hoping for a more general classification or subclass of planar modular or pseudomodular graphs; the existence of a unique median, in particular, is a little too strong of a condition $\endgroup$
    – mich
    Sep 3 '16 at 11:03
  • 1
    $\begingroup$ I posted another partial answer (the graphs of 2d modular lattices) on my blog at 11011110.livejournal.com/334654.html — but I think this still is far from a more general classification. $\endgroup$ Sep 7 '16 at 7:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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