License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CPM.2018.10
URN: urn:nbn:de:0030-drops-86992
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8699/
Go to the corresponding LIPIcs Volume Portal

Akutsu, Tatsuya ; de la Higuera, Colin ; Tamura, Takeyuki

A Simple Linear-Time Algorithm for Computing the Centroid and Canonical Form of a Plane Graph and Its Applications

pdf-format:
LIPIcs-CPM-2018-10.pdf (0.5 MB)

Abstract

We present a simple linear-time algorithm for computing the topological centroid and the canonical form of a plane graph. Although the targets are restricted to plane graphs, it is much simpler than the linear-time algorithm by Hopcroft and Wong for determination of the canonical form and isomorphism of planar graphs. By utilizing a modified centroid for outerplanar graphs, we present a linear-time algorithm for a geometric version of the maximum common connected edge subgraph (MCCES) problem for the special case in which input geometric graphs have outerplanar structures, MCCES can be obtained by deleting at most a constant number of edges from each input graph, and both the maximum degree and the maximum face degree are bounded by constants.

BibTeX - Entry

@InProceedings{akutsu_et_al:LIPIcs:2018:8699,
  author =	{Tatsuya Akutsu and Colin de la Higuera and Takeyuki Tamura},
  title =	{{A Simple Linear-Time Algorithm for Computing the Centroid and Canonical Form of a Plane Graph and Its Applications}},
  booktitle =	{Annual Symposium on Combinatorial Pattern Matching  (CPM 2018)},
  pages =	{10:1--10:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-074-3},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{105},
  editor =	{Gonzalo Navarro and David Sankoff and Binhai Zhu},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2018/8699},
  URN =		{urn:nbn:de:0030-drops-86992},
  doi =		{10.4230/LIPIcs.CPM.2018.10},
  annote =	{Keywords: Plane graph, Graph isomorphism, Maximum common subgraph}
}

Keywords: Plane graph, Graph isomorphism, Maximum common subgraph
Collection: Annual Symposium on Combinatorial Pattern Matching (CPM 2018)
Issue Date: 2018
Date of publication: 18.05.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI