A graph is outer-1-planar if it can be drawn in the plane so that all vertices are on the outer face and each edge is crossed at most once. Zhang et al. (Edge covering pseudoouterplanar graphs with forests, Discrete Math 312:2788-2799, 2012; MR2945171) proved that the linear arboricity of every outer-1-planar graph with maximum degree △ is exactly 「△/2」 provided that △ = 3 or △ ≥ 5 and claimed that there are outer-1-planar graphs with maximum degree △ = 4 and linear arboricity 「(△ + 1)/2」 = 3. It is shown in this paper that the linear arboricity of every outer-1-planar graph with maximum degree 4 is exactly 2 provided that it admits an outer-1-planar drawing with crossing distance at least 1 and crossing width at least 2, and moreover, none of the above constraints on the crossing distance and crossing width can be removed. Besides, a polynomial-time algorithm for constructing a path-2-coloring (i.e., an edge 2-coloring such that each color class induces a linear forest, a disjoint union of paths) of such an outer-1-planar drawing is given.
Xin Zhang, Bi Li
. Linear Arboricity of Outer-1-Planar Graphs[J]. Journal of the Operations Research Society of China, 2021
, 9(1)
: 181
-193
.
DOI: 10.1007/s40305-019-00243-2
[1] Bondy, J.A., Murty, U.S.R.:Graph Theory with Applications. North-Holland, New York (1976)
[2] Harary, F.:Covering and packing in graphs I. Ann. N. Y. Acad. Sci. 175, 198-205(1970)
[3] Akiyama, J., Exoo, G., Harary, F.:Covering and packing in graphs Ⅲ:cyclic and acyclic invariants. Math. Slovaca 30, 405-417(1980)
[4] Wu, J.L.:On the linear arboricity of planar graphs. J. Graph Theory 31, 129-134(1999)
[5] Wu, J.L., Wu, Y.:The linear arboricity of planar graphs of maximum degree seven are four. J. Graph Theory 58, 210-220(2008)
[6] Cygan, M., Hou, J., Kowalik, Ł., Lužar, B., Wu, J.L.:A planar linear arboricity. J. Graph Theory 69(4), 403-425(2012)
[7] Wu, J.L.:The linear arboricity of series-parallel graphs. Graphs Comb. 16, 367-372(2000)
[8] Peroche, B.:Complexity of the linear arboricity of a graph. RAIRO Oper. Res. 16, 125-129(1982). In French
[9] Eggleton, R.B.:Rectilinear drawings of graphs. Util. Math. 29, 149-172(1986)
[10] Zhang, X., Liu, G., Wu, J.L.:Edge covering pseudo-outerplanar graphs with forests. Discrete Math. 312, 2788-2799(2012)
[11] Zhang, X.:List total coloring of pseudo-outerplanar graphs. Discrete Math. 313, 2297-2306(2013)
[12] Auer, C., Bachmaier, C., Brandenburg, F.J., et al.:Outer-1-planar graphs. Algorithmica 74, 1293-1320(2016)
[13] Dehkordi, H.R., Eades, P.:Every outer-1-plane graph has a right angle crossing drawing. Int. J. Comput. Geom. Appl. 22, 543-557(2012)
[14] Auer, C., Bachmaier, C., Brandenburg, F.J., et al.:Recognizing outer 1-planar graphs in linear time. Lect. Notes Comput. Sci. 8242, 107-118(2013)
[15] Hong, S.-H., Eades, P., Katoh, N., et al.:A linear-time algorithm for testing outer-1-planarity. Algorithmica 72, 1033-1054(2015)
