首页 | 本学科首页   官方微博 | 高级检索  
     


Odd Crossing Number and Crossing Number Are Not the Same
Authors:Michael J. Pelsmajer  Marcus Schaefer  Daniel Štefankovič
Affiliation:(1) Department of Applied Mathematics, Illinois Institute of Technology, Chicago, IL 60616, USA;(2) Department of Computer Science, DePaul University, Chicago, IL 60604, USA;(3) Computer Science Department, University of Rochester, Rochester, NY 14627-0226, USA
Abstract:The crossing number of a graph is the minimum number of edge intersections in a plane drawing of a graph, where each intersection is counted separately. If instead we count the number of pairs of edges that intersect an odd number of times, we obtain the odd crossing number. We show that there is a graph for which these two concepts differ, answering a well-known open question on crossing numbers. To derive the result we study drawings of maps (graphs with rotation systems).
Keywords:
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号