Edge-disjoint maximal planar graphs

✍ Scribed by Sharon G. Boswell; Jamie Simpson

• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 316 KB
• Volume: 179
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/s0012-365x(97)00095-2

✦ Synopsis

We show that if n >~6m then it is possible to construct m edge-disjoint maximal planar graphs on a set of n vertices, but that it is not possible if n < 6m -1. We also show that given a pair of edge-disjoint maximal planar graphs, and a specified face in one, there exist at least three faces in the other which are vertex-disjoint from the specified face. For three edge-disjoint maximal planar graphs there exist three faces, one from each graph, which are vertex-disjoint.