On polygon numbers of circle graphs and distance hereditary graphs

DOI10.1016/j.dam.2017.09.016zbMath1395.05088arXiv1401.1541OpenAlexW2962706559MaRDI QIDQ2413962

Richard Valenzano, Lorna K. 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

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

Mathematics Subject Classification ID

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

Related Items (2)

Unnamed Item ⋮ Mim-width. II. The feedback vertex set problem

Cites Work

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

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