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

Voir la notice de l'article provenant de la source The Electronic Journal of Combinatorics website

Zbl arXiv EuDML
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 
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
@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

Cité par Sources :