Name
Abstract | ||
|---|---|---|
We prove that the Weisfeiler--Leman (WL) dimension of the class of all finite planar graphs is at most 3. In particular, every finite planar graph is definable in first-order logic with counting using at most 4 variables. The previously best-known upper bounds for the dimension and number of variables were 14 and 15, respectively.
First, we show that, for dimension 3 and higher, the WL-algorithm correctly tests isomorphism of graphs in a minor-closed class whenever it determines the orbits of the automorphism group of every arc-colored 3-connected graph belonging to this class.
Then, we prove that, apart from several exceptional graphs (which have WL-dimension at most 2), the individualization of two appropriately chosen vertices of a colored 3-connected planar graph followed by the one-dimensional WL-algorithm produces the discrete vertex partition. This implies that the three-dimensional WL-algorithm determines the orbits of arc-colored 3-connected planar graphs.
As a byproduct of the proof, we get a classification of the 3-connected planar graphs with fixing number 3.
|
Year | DOI | Venue |
|---|---|---|
2019 | 10.1145/3333003 | Journal of the ACM |
Keywords | Field | DocType |
First-order logic with counting,Weisfeiler--Leman algorithm,isomorphism testing,planar graphs | Discrete mathematics,Combinatorics,Computer science,Planar graph | Journal |
Volume | Issue | ISSN |
66 | 6 | 0004-5411 |
Citations | PageRank | References |
1 | 0.35 | 16 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sandra Kiefer | 1 | 9 | 2.50 |
| Ilia N. Ponomarenko | 2 | 40 | 7.24 |
| Pascal Schweitzer | 3 | 214 | 16.94 |