On polygon numbers of circle graphs and distance hereditary graphs

DOI10.1016/J.DAM.2017.09.016MaRDI QIDQ2413962zbMATH OpenOpenAlexFDO

Authors Richard Valenzano, Lorna Stewart

Publication date 17 September 2018

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1401.1541

zbMATH Keywords

\(k\)-polygon graphasteroidal numbercircle graphdistance hereditary graphpermutation graphpolygon number

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph theory (05C99)

Abstract: Circle graphs are intersection graphs of chords in a circle and $k$-polygon graphs are intersection graphs of chords in a convex $k$-sided polygon where each chord has its endpoints on distinct sides. The $k$-polygon graphs, for $kge2$, form an infinite chain of graph classes, each of which contains the class of permutation graphs. The union of all of those graph classes is the class of circle graphs. The polygon number $gp(G)$ of a circle graph $G$ is the minimum $k$ such that $G$ is a $k$-polygon graph. Given a circle graph $G$ and an integer $k$, determining whether $gp(G)lek$ is NP-complete, while the problem is solvable in polynomial time for fixed $k$. In this paper, we show that $gp(G)$ is always at least as large as the asteroidal number of $G$, and equal to the asteroidal number of $G$ when $G$ is a connected distance hereditary graph that is not a clique. This implies that the classes of distance hereditary permutation graphs and distance hereditary AT-free graphs are the same, and we give a forbidden subgraph characterization of that class. We also establish the following upper bounds: $gp(G)$ is at most the clique cover number of $G$ if $G$ is not a clique, at most 1 plus the independence number of $G$, and at most $lceiln/2ceil$ where $nge3$ is the number of vertices of $G$. Our results lead to linear time algorithms for finding the minimum number of corners that must be added to a given circle representation to produce a polygon representation, and for finding the asteroidal number of a distance hereditary graph, both of which are improvements over previous algorithms for those problems.

Recommendations

• Publication:5753980
• Distance Hereditary Graphs and the Interlace Polynomial
• On the geodetic iteration number of distance-hereditary graphs
• An exact enumeration of distance-hereditary graphs
• Circular chromatic numbers of a class of distance graphs
• On an extension of distance-hereditary graphs
• On an extension of distance hereditary graphs
• scientific article; zbMATH DE number 2058270
• Circular chromatic numbers of some distance graphs
• Diameter graphs of polygons and the proof of a conjecture of Graham

Cites work

• A characterization of ptolemaic graphs
• A Combinatorial Decomposition Theory
• Algorithmic graph theory and perfect graphs
• Algorithms for a maximum clique and a maximum independent set of a circle graph
• Algorithms on circular-arc graphs
• An Efficient Test for Circular-Arc Graphs
• An O(n2) Algorithm for Undirected Split Decomposition
• Approximating Bandwidth by Mixing Layouts of Interval Graphs
• Approximating the minimum clique cover and other hard problems in subtree filament graphs
• Bipartite graphs that are not circle graphs
• Collective additive tree spanners for circle graphs and polygonal graphs
• Comparability graphs and intersection graphs
• Completely separable graphs
• Decomposition of Directed Graphs
• Distance-hereditary comparability graphs
• Distance-hereditary graphs
• Graph Classes: A Survey
• scientific article; zbMATH DE number 53952 (Why is no real title available?)
• scientific article; zbMATH DE number 1107735 (Why is no real title available?)
• Independence and domination in polygon graphs
• Linear time algorithms on circular-arc graphs
• Linear time split decomposition revisited
• Parallel Algorithms for Hierarchical Clustering and Applications to Split Decomposition and Parity Graph Recognition
• Polygon Graph Recognition
• Practical and efficient circle graph recognition
• Recognition of Circle Graphs
• Recognizing circle graphs in polynomial time
• Reducing prime graphs and recognizing circle graphs
• The complexity of colouring circle graphs (extended abstract)
• Transitiv orientierbare Graphen
• Treewidth. Computations and approximations

Cited in

(4)

• Mim-width. II. The feedback vertex set problem
• A unified polynomial-time algorithm for feedback vertex set on graphs of bounded mim-width
• Polygon Graph Recognition
• Obstructions to faster diameter computation: asteroidal sets

This page was built for publication: On polygon numbers of circle graphs and distance hereditary graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2413962)