Subgraph Isomorphism in Planar Graphs and Related Problems

Simple item page
dc.creatorEppstein, David
dc.date1999-11-09
dc.date.accessioned2026-07-07T03:24:26Z
dc.date.available2026-07-07T03:24:26Z
dc.descriptionWe solve the subgraph isomorphism problem in planar graphs in linear time, for any pattern of constant size. Our results are based on a technique of partitioning the planar graph into pieces of small tree-width, and applying dynamic programming within each piece. The same methods can be used to solve other planar graph problems including connectivity, diameter, girth, induced subgraph isomorphism, and shortest paths.
dc.description27 pages, 6 figures. A preliminary version of this paper appeared at the 6th ACM-SIAM Symp. Discrete Algorithms, 1995
dc.identifierhttps://arxiv.org/abs/cs/9911003
dc.identifierhttp://arxiv.org/abs/cs/9911003
dc.identifierJ. Graph Algorithms & Applications 3(3):1-27, 1999
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/33325
dc.subjectData Structures and Algorithms
dc.subjectF.2.2
dc.titleSubgraph Isomorphism in Planar Graphs and Related Problems
dc.typetext

Files

Collections

arXiv