Algorithms that exploit the structure of graphs that can be drawn on a plane without crossing edges. Baker's technique designs polynomial-time approximation schemes for hard problems on planar graphs by breaking the graph into layers, solving each layer optimally and combining the results, and a Pfaffian orientation assigns directions to edges so that perfect matchings can be counted, which is the idea behind the FKT algorithm for planar graphs. An algorithm belongs here when its cited article describes a technique that works on planar graphs or on closely related graph classes. It excludes general matching and flow algorithms, which have their own group.
Browse By
Planar Graph Algorithms
Filter Results2 entries
Sources
Wikipedia: Baker's technique
Has Member: Baker's Technique, IntroductionQuote, Has Member: Baker's Technique, Introduction
In theoretical computer science, Baker's technique is a method for designing polynomial-time approximation schemes (PTASs) for problems on planar graphs.
Wikipedia: Pfaffian orientation
Has Member: Pfaffian Orientation, IntroductionQuote, Has Member: Pfaffian Orientation, Introduction
This is the main idea behind the FKT algorithm for counting perfect matchings in planar graphs, which always have Pfaffian orientations.
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.