Publications and Research

Document Type

Article

Publication Date

2009

Abstract

We extend known results regarding the maximum rectilinear crossing number of the cycle graph (Cn) and the complete graph (Kn ) to the class of general d-regular graphs Rn,d. We present the generalized star drawings of the d-regular graphs Sn,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 Sn,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.

 
 

To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.