The Maximum of the Maximum Rectilinear Crossing Numbers of d-regular Graphs of Order n

Details The Maximum of the Maximum Rectilinear Crossing Numbers of d-regular Graphs of Order n The Maximum of the Maximum Rectilinear Crossing Numbers of d-regular Graphs of Order n

2008-12-10

arxiv.org/abs/0812.1917v1

Mathematics

Combinatorics

21 pages, 7 figures; submitted

Scientific paper

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= 1 mod 2 and prove that they maximize the maximum rectilinear crossing numbers. A star-like drawing of S_{n,d} for n = d = 0 mod 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.

Affiliated with

Also associated with

No associations

Rating

The Maximum of the Maximum Rectilinear Crossing Numbers of d-regular Graphs of Order n does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The Maximum of the Maximum Rectilinear Crossing Numbers of d-regular Graphs of Order n, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Maximum of the Maximum Rectilinear Crossing Numbers of d-regular Graphs of Order n will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-527637