Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userForbidden structure characterization of circular-arc graphs and a certifying recognition algorithm
695
0
0.0
(
0
)
Added by
Mathew Francis
Publication date
2014
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
A circular-arc graph is the intersection graph of arcs of a circle. It is a well-studied graph model with numerous natural applications. A certifying algorithm is an algorithm that outputs a certificate, along with its answer (be it positive or negative), where the certificate can be used to easily justify the given answer. While the recognition of circular-arc graphs has been known to be polynomial since the 1980s, no polynomial-time certifying recognition algorithm is known to date, despite such algorithms being found for many subclasses of circular-arc graphs. This is largely due to the fact that a forbidden structure characterization of circular-arc graphs is not known, even though the problem has been intensely studied since the seminal work of Klee in the 1960s. In this contribution, we settle this problem. We present the first forbidden structure characterization of circular-arc graphs. Our obstruction has the form of mutually avoiding walks in the graph. It naturally extends a similar obstruction that characterizes interval graphs. As a consequence, we give the first polynomial-time certifying algorithm for the recognition of circular-arc graphs.
rate research
Read More
In this short note, we show two NP-completeness results regarding the emph{simultaneous representation problem}, introduced by Lubiw and Jampani. The simultaneous representation problem for a given class of intersection graphs asks if some $k$ graphs can be represented so that every vertex is represented by the same interval in each representation. We prove that it is NP-complete to decide this for the class of interval and circular-arc graphs in the case when $k$ is a part of the input and graphs are not in a sunflower position.
The partial representation extension problem, introduced by Klav{i}k et al. (2011), generalizes the recognition problem. In this short note we show that this problem is NP-complete for unit circular-arc graphs.
A pair of non-adjacent edges is said to be separated in a circular ordering of vertices, if the endpoints of the two edges do not alternate in the ordering. The circular separation dimension of a graph $G$, denoted by $pi^circ(G)$, is the minimum number of circular orderings of the vertices of $G$ such that every pair of non-adjacent edges is separated in at least one of the circular orderings. This notion is introduced by Loeb and West in their recent paper. In this article, we consider two subclasses of planar graphs, namely $2$-outerplanar graphs and series-parallel graphs. A $2$-outerplanar graph has a planar embedding such that the subgraph obtained by removal of the vertices of the exterior face is outerplanar. We prove that if $G$ is $2$-outerplanar then $pi^circ(G) = 2$. We also prove that if $G$ is a series-parallel graph then $pi^circ(G) leq 2$.
A graph is said to be circular-arc if the vertices can be associated with arcs of a circle so that two vertices are adjacent if and only if the corresponding arcs overlap. It is proved that the isomorphism of circular-arc graphs can be tested by the Weisfeiler-Leman algorithm after individualization of two vertices.
A homogeneous set of a graph $G$ is a set $X$ of vertices such that $2le lvert Xrvert <lvert V(G)rvert$ and no vertex in $V(G)-X$ has both a neighbor and a non-neighbor in $X$. A graph is prime if it has no homogeneous set. We present an algorithm to decide whether a class of graphs given by a finite set of forbidden induced subgraphs contains infinitely many non-isomorphic prime graphs.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
