FACETS IN THE CROSSING NUMBER POLYTOPE

被引：2
作者：
Chimani, Markus [1 ]
机构：
[1] Univ Jena, Jena, Germany
来源：
SIAM JOURNAL ON DISCRETE MATHEMATICS | 2011年 / 25卷 / 01期
关键词：
crossing number; integer linear program; polyhedral study; facets; Kuratowski constraints;
D O I：
10.1137/09076965X
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
In the last years, several integer linear programming (ILP) formulations for the crossing number problem arose. While they all contain a common conceptual core, the properties of the corresponding polytopes have never been investigated. In this paper, we formally establish the crossing number polytope and show several facet-defining constraint classes.
引用
收藏
页码：95 / 111
页数：17
相关论文
共 50 条
[31]   On the Degenerate Crossing Number [J].
Ackerman, Eyal ;
Pinchasi, Rom .
DISCRETE & COMPUTATIONAL GEOMETRY, 2013, 49 (03) :695-702
[32]   The genus crossing number [J].
Mohar, Bojan .
ARS MATHEMATICA CONTEMPORANEA, 2009, 2 (02) :157-162
[33]   THE CROSSING NUMBER OF POSETS [J].
LIN, C .
ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS, 1994, 11 (02) :169-193
[34]   Monotone Crossing Number [J].
Pach, Janos ;
Toth, Geza .
GRAPH DRAWING, 2012, 7034 :278-289
[35]   Applications of the crossing number [J].
Pach, J ;
Shahrokhi, F ;
Szegedy, M .
ALGORITHMICA, 1996, 16 (01) :111-117
[36]   Chromatic Number, Independence Ratio, and Crossing Number [J].
Albertson, Michael O. .
ARS MATHEMATICA CONTEMPORANEA, 2008, 1 (01) :1-6
[37]   Improvement on the Crossing Number of Crossing-Critical Graphs [J].
Barat, Janos ;
Toth, Geza .
DISCRETE & COMPUTATIONAL GEOMETRY, 2022, 67 (02) :595-604
[38]   Bounding the crossing number of a graph in terms of the crossing number of a minor with small maximum degree [J].
Garcia-Moreno, E ;
Salazar, G .
JOURNAL OF GRAPH THEORY, 2001, 36 (03) :168-173
[39]   Improvement on the Crossing Number of Crossing-Critical Graphs [J].
János Barát ;
Géza Tóth .
Discrete & Computational Geometry, 2022, 67 :595-604
[40]   On the Crossing Number of Cartesian Products [J].
Drazenska, Emilia .
MATHEMATICAL METHODS IN ECONOMICS (MME 2014), 2014, :180-184
12345