×

zbMATH — the first resource for mathematics

Notes on a theorem of Naji. (English) Zbl 1347.05096
Summary: We present a new proof of an algebraic characterization of circle graphs due to W. Naji [ibid. 54, 329–337 (1985; Zbl 0567.05033)].
For bipartite graphs, Naji’s theorem is equivalent to an algebraic characterization of planar matroids due to J. Geelen and B. Gerards [J. Comb. Theory, Ser. B 103, No. 5, 642–646 (2013; Zbl 1408.05029)]. Naji’s theorem also yields an algebraic characterization of permutation graphs.

MSC:
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
05C38 Paths and cycles
05B35 Combinatorial aspects of matroids and geometric lattices
05C10 Planar graphs; geometric and topological aspects of graph theory
52B40 Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bandelt, H. J.; Mulder, H. M., Distance-hereditary graphs, J. Combin. Theory Ser. B, 41, 182-208, (1986) · Zbl 0605.05024
[2] Bonomo, F.; Durán, G.; Grippo, L. N.; Safe, M. D., Partial characterizations of circle graphs, Discrete Appl. Math., 159, 1699-1706, (2011) · Zbl 1228.05243
[3] Bouchet, A., Caractérisation des symboles croisés de genre nul, C. R. Acad. Sci. Paris Sér. A-B, 274, A724-A727, (1972)
[4] Bouchet, A., Reducing prime graphs and recognizing circle graphs, Combinatorica, 7, 243-254, (1987) · Zbl 0666.05037
[5] Bouchet, A., Graphic presentation of isotropic systems, J. Combin. Theory Ser. B, 45, 58-76, (1988) · Zbl 0662.05014
[6] Bouchet, A., Circle graph obstructions, J. Combin. Theory Ser. B, 60, 107-144, (1994) · Zbl 0793.05116
[7] Bouchet, A., Bipartite graphs that are not circle graphs, Ann. Inst. Fourier (Grenoble), 49, 809-814, (1999) · Zbl 0917.05064
[8] Brahana, H. R., Systems of circuits on two-dimensional manifolds, Ann. of Math., 23, 144-168, (1921) · JFM 48.0661.02
[9] Cohn, M.; Lempel, A., Cycle decomposition by disjoint transpositions, J. Combin. Theory Ser. A, 13, 83-89, (1972) · Zbl 0314.05005
[10] R. Brijder, L. Traldi, Isotropic matroids. II. Circle graphs, 2015. arXiv:1504.04299. · Zbl 1351.05044
[11] R. Brijder, L. Traldi, Isotropic matroids. III. Connectivity, 2016. arXiv:1602.03899. · Zbl 1366.05062
[12] Courcelle, B., Circle graphs and monadic second-order logic, J. Appl. Log., 6, 416-442, (2008) · Zbl 1149.03011
[13] Cunningham, W. H., Decomposition of directed graphs, SIAM J. Algebr. Discrete Methods, 3, 214-228, (1982) · Zbl 0497.05031
[14] Daligault, J.; Gonçalves, D.; Rao, M., Diamond-free circle graphs are Helly circle, Discrete Math., 310, 845-849, (2010) · Zbl 1222.05033
[15] de Fraysseix, H., Local complementation and interlacement graphs, Discrete Math., 33, 29-35, (1981) · Zbl 0448.05024
[16] Even, S.; Itai, A., Queues, stacks, and graphs, (Theory of Machines and Computations (Proc. Internat. Sympos., Technion, Haifa, 1971), (1971), Academic Press New York), 71-86
[17] Gabor, C.; Supowit, K.; Hsu, W.-L., Recognizing circle graphs in polynomial time, J. Assoc. Comput. Mach., 36, 435-473, (1989) · Zbl 0825.68417
[18] Gasse, E., A proof of a circle graph characterization, Discrete Math., 173, 223-238, (1997)
[19] J.F. Geelen, Matchings, matroids, and unimodular matrices (Thesis), Waterloo, 1995
[20] Geelen, J.; Gerards, B., Characterizing graphic matroids by a system of linear equations, J. Combin. Theory Ser. B, 103, 642-646, (2013) · Zbl 1408.05029
[21] Gioan, E.; Paul, C.; Tedder, M.; Corneil, D., Practical and efficient circle graph recognition, Algorithmica, 69, 759-788, (2014) · Zbl 1303.05190
[22] Golumbic, M. C., Algorithmic Graph Theory and Perfect Graphs, (1980), Academic Press New York · Zbl 0541.05054
[23] W. Naji, Graphes de cordes: une caracterisation et ses applications (Thèse), Grenoble, 1985
[24] Naji, W., Reconnaissance des graphes de cordes, Discrete Math., 54, 329-337, (1985) · Zbl 0567.05033
[25] Read, R. C.; Rosenstiehl, P., On the Gauss crossing problem, (Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. II, Colloq. Math. Soc. János Bolyai, vol. 18, (1978), North-Holland Amsterdam, New York), 843-876
[26] Spinrad, J., Recognition of circle graphs, J. Algorithms, 16, 264-282, (1994) · Zbl 0797.68130
[27] Zelinka, B., The graph of the system of chords of a given circle, Mat.-Fyz. Časopis Sloven. Akad. Vied, 15, 273-279, (1965) · Zbl 0142.41601
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.