Geodesic
The maximum of the maximum rectilinear crossing numbers of \(d\)-regular graphs of order \(n\)
The electronic journal of combinatorics, Tome 16 (2009) no. 1
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

We extend known results regarding the maximum rectilinear crossing number of the cycle graph ($C_n$) and the complete graph ($K_n$) to the class of general $d$-regular graphs $R_{n,d}$. We present the generalized star drawings of the $d$-regular graphs $S_{n,d}$ of order $n$ where $n+d\equiv 1 \pmod 2 $ and prove that they maximize the maximum rectilinear crossing numbers. A star-like drawing of $S_{n,d}$ for $n \equiv d \equiv 0 \pmod 2$ is introduced and we conjecture that this drawing maximizes the maximum rectilinear crossing numbers, too. We offer a simpler proof of two results initially proved by Furry and Kleitman as partial results in the direction of this conjecture.
DOI : 10.37236/143
Classification : 05C35, 05C10
Mots-clés : maximum rectilinear crossing number, cycle graph, complete graph, regular graphs, generalized star drawings, star like drawings 
@article{10_37236_143,
     author = {Matthew Alpert and Elie Feder and Heiko Harborth},
     title = {The maximum of the maximum rectilinear crossing numbers of \(d\)-regular graphs of order \(n\)},
     journal = {The electronic journal of combinatorics},
     year = {2009},
     volume = {16},
     number = {1},
     doi = {10.37236/143},
     zbl = {1179.05054},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/143/}
}
TY  - JOUR
AU  - Matthew Alpert
AU  - Elie Feder
AU  - Heiko Harborth
TI  - The maximum of the maximum rectilinear crossing numbers of \(d\)-regular graphs of order \(n\)
JO  - The electronic journal of combinatorics
PY  - 2009
VL  - 16
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.37236/143/
DO  - 10.37236/143
ID  - 10_37236_143
ER  - 
%0 Journal Article
%A Matthew Alpert
%A Elie Feder
%A Heiko Harborth
%T The maximum of the maximum rectilinear crossing numbers of \(d\)-regular graphs of order \(n\)
%J The electronic journal of combinatorics
%D 2009
%V 16
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/143/
%R 10.37236/143
%F 10_37236_143
Matthew Alpert; Elie Feder; Heiko Harborth. The maximum of the maximum rectilinear crossing numbers of \(d\)-regular graphs of order \(n\). The electronic journal of combinatorics, Tome 16 (2009) no. 1. doi: 10.37236/143

Cité par Sources :