Name
Abstract | ||
|---|---|---|
Graph isomorphism is an important and widely studied computational problem with a yet unsettled complexity. However, the exact complexity is known for isomorphism of various classes of graphs. Recently, (8) proved that planar isomorphism is complete for log-space. We extend this result further to the classes of graphs which exclude K3,3 or K5 as a minor, and give a log-space algorithm. Our algorithm decomposes K3,3 minor-free graphs into biconnected and those further into tricon- nected components, which are known to be either planar or K5 components (20). This gives a tricon- nected component tree similar to that for planar graphs. An extension of the log-space algorithm of (8) can then be used to decide the isomorphism problem. For K5 minor-free graphs, we consider 3-connected components. These are either planar or isomor- phic to the four-rung mobius ladder on 8 vertices or, with a further decomposition, one obtains planar 4-connected components (9). We give an algorithm to get a unique decomposition of K5 minor-free graphs into bi-, tri- and 4-connected components, and construct trees, accordingly. Since the algorithm of (8) does not deal with four-connected component trees, it needs to be modified in a quite non-trivial way. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.4230/LIPIcs.FSTTCS.2009.2314 | FSTTCS |
Keywords | Field | DocType |
planar graph,graph isomorphism,connected component | Discrete mathematics,Combinatorics,Indifference graph,Modular decomposition,Graph isomorphism,Graph homomorphism,Chordal graph,Induced subgraph isomorphism problem,Pathwidth,Planar graph,Mathematics | Conference |
Citations | PageRank | References |
9 | 0.51 | 9 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Samir Datta | 1 | 200 | 19.82 |
| Prajakta Nimbhorkar | 2 | 170 | 15.04 |
| Thomas Thierauf | 3 | 288 | 33.59 |
| Fabian Wagner | 4 | 20 | 3.87 |