Simple planar graph partition into three forests

✍ Scribed by Roberto Grossi; Elena Lodi

• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 796 KB
• Volume: 84
• Category: Article
• ISSN: 0166-218X
• DOI: 10.1016/s0166-218x(98)00007-9

✦ Synopsis

We describe a simple way of partitioning a planar graph into three edge-disjoint forests in O(n log n) time, where n is the number of its vertices. We can use this partition in Kannan et al.'s graph representation (1992) to label the planar graph vertices so that any two vertices' adjacency can be tested locally by comparing their names in constant time.