Extending Partial Representations of Circle Graphs

Chaplick, Steven and Fulek, Radoslav and Klavík, Pavel (2013) Extending Partial Representations of Circle Graphs. In: 21st International Symposium, GD 2013, September 23-25, 2013, Bordeaux, France , pp. 131-142 (Official URL: http://dx.doi.org/10.1007/978-3-319-03841-4_12).

Full text not available from this repository.


The partial representation extension problem is a recently introduced generalization of the recognition problem. A circle graph is an intersection graph of chords of a circle. We study the partial representation extension problem for circle graphs, where the input consists of a graph G and a partial representation R′ giving some pre-drawn chords that represent an induced subgraph of G. The question is whether one can extend R′ to a representation R of the entire G, i.e., whether one can draw the remaining chords into a partially pre-drawn representation. Our main result is a polynomial-time algorithm for partial representation extension of circle graphs. To show this, we describe the structure of all representation a circle graph based on split decomposition. This can be of an independent interest.

Item Type:Conference Paper
Classifications:Z Theory > Z.250 Geometry
Z Theory > Z.500 Representations
ID Code:1367

Repository Staff Only: item control page


Angelini, P., Battista, G.D., Frati, F., Jelínek, V., Kratochvíl, J., Patrignani, M., Rutter, I.: Testing planarity of partially embedded graphs. In: SODA 2010, pp. 202–221 (2010)

Balko, M., Klavík, P., Otachi, Y.: Bounded representations of interval and proper interval graphs. In: ISAAC (to appear, 2013)

Bläsius, T., Rutter, I.: Simultaneous PQ-ordering with applications to constrained embedding problems. In: SODA 2013, pp. 1030–1043 (2013)

Bouchet, A.: Reducing prime graphs and recognizing circle graphs. Combinatorica 7(3), 243–254 (1987)

Bouchet, A.: Unimodularity and circle graphs. Discrete Mathematics 66(1-2), 203–208 (1987)

Chudnovsky, M., Robertson, N., Seymour, P., Thomas, R.: The strong perfect graph theorem. Annals of Mathematics 164, 51–229 (2006)

Courcelle, B.: Circle graphs and monadic second-order logic. J. Applied Logic 6(3), 416–442 (2008)

Cunningham, W.: Decomposition of directed graphs. SIAM J. Alg. and Disc. Methods 3, 214–228 (1982)

Dahlhaus, E.: Parallel algorithms for hierarchical clustering and applications to split decomposition and parity graph recognition. Journal of Algorithms 36(2), 205–240 (1998)

de Fraysseix, H.: Local complementation and interlacement graphs. Discrete Mathematics 33(1), 29–35 (1981)

de Fraysseix, H., de Mendez, P.O.: On a characterization of gauss codes. Discrete & Computational Geometry 22(2), 287–295 (1999)

Even, S., Itai, A.: Queues, stacks, and graphs. In: Kohavi, Z., Paz, A. (eds.) Theory of Machines and Computation, pp. 71–76 (1971)

Gabor, C.P., Supowit, K.J., Hsu, W.: Recognizing circle graphs in polynomial time. J. ACM 36(3), 435–473 (1989)

Gioan, E., Paul, C., Tedder, M., Corneil, D.: Practical and efficient circle graph recognition. Algorithmica, 1–30 (2013)

Jampani, K.R., Lubiw, A.: The simultaneous representation problem for chordal, comparability and permutation graphs. Journal of Graph Algortihms and Applications 16(2), 283–315 (2012)

Klavík, P., Kratochvíl, J., Krawczyk, T., Walczak, B.: Extending partial representations of function graphs and permutation graphs. In: Epstein, L., Ferragina, P. (eds.) ESA 2012. LNCS, vol. 7501, pp. 671–682. Springer, Heidelberg (2012)

Klavík, P., Kratochvíl, J., Otachi, Y., Rutter, I., Saitoh, T., Saumell, M., Vyskočil, T.: Extending partial representations of proper and unit interval graphs (in preparation, 2013)

Klavík, P., Kratochvíl, J., Otachi, Y., Saitoh, T.: Extending partial representations of subclasses of chordal graphs. In: Chao, K.-M., Hsu, T.-S., Lee, D.-T. (eds.) ISAAC 2012. LNCS, vol. 7676, pp. 444–454. Springer, Heidelberg (2012)

Klavík, P., Kratochvíl, J., Vyskočil, T.: Extending partial representations of interval graphs. In: Ogihara, M., Tarui, J. (eds.) TAMC 2011. LNCS, vol. 6648, pp. 276–285. Springer, Heidelberg (2011)

Kostochka, A., Kratochvíl, J.: Covering and coloring polygon-circle graphs. Discrete Mathematics 163(1-3), 299–305 (1997)

Naji, W.: Graphes de Cordes: Une Caracterisation et ses Applications. PhD thesis, l’Université Scientifique et Médicale de Grenoble (1985)

Oum, S.: Rank-width and vertex-minors. J. Comb. Theory, Ser. B 95(1), 79–100 (2005)

Patrignani, M.: On extending a partial straight-line drawing. In: Healy, P., Nikolov, N.S. (eds.) GD 2005. LNCS, vol. 3843, pp. 380–385. Springer, Heidelberg (2006)

Spinrad, J.P.: Recognition of circle graphs. J. of Algorithms 16(2), 264–282 (1994)

Spinrad, J.P.: Efficient Graph Representations. Field Institute Monographs (2003)