Circle Graph Recognition in Time $O(n+m) α(n+m)$

Details Circle Graph Recognition in Time $O(n+m) α(n+m)$ Circle Graph Recognition in Time $O(n+m) α(n+m)$

2011-04-17

arxiv.org/abs/1104.3284v2

Computer Science

Data Structures and Algorithms

Scientific paper

Circle graphs are the intersection graphs of chords in a circle. This paper presents the first sub-quadratic recognition algorithm for the class of circle graphs. Our algorithm is $O(n+m)$ times the inverse Ackermann function, $\alpha(n+m)$, whose value is smaller than 4 for any practical graph. The algorithm is based on a new incremental Lexicographic Breadth-First Search characterization of circle graphs, and a new efficient data-structure for circle graphs, both developed in the paper. The algorithm is an extension of a Split Decomposition algorithm with same running time developed by the authors in a companion paper.

Affiliated with

Also associated with

No associations

Rating

Circle Graph Recognition in Time $O(n+m) α(n+m)$ does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Circle Graph Recognition in Time $O(n+m) α(n+m)$, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Circle Graph Recognition in Time $O(n+m) α(n+m)$ will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-394194