Premium
New facets for the planar subgraph polytope
Author(s) -
Hicks Illya V.
Publication year - 2008
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20207
Subject(s) - polytope , subdivision , combinatorics , facet (psychology) , mathematics , class (philosophy) , planar , star (game theory) , set (abstract data type) , polytope model , enhanced data rates for gsm evolution , computer science , artificial intelligence , computer graphics (images) , psychology , social psychology , mathematical analysis , archaeology , personality , big five personality traits , history , programming language
This study describes certain facet classes for the planar subgraph polytope. These facets are extensions of Kuratowski facets and are of the form 2 x ( U ) + x ( E ( G )\ U ) ≤ 2| U | + | E ( G )\ U | − 2 where the edge set U varies and can be empty. Two of the new types of facets complete the class of extended subdivision facets, explored by Jünger and Mutzel. In addition, the other types of facets consist of a new class of facets for the polytope called 3‐star subdivisions. It is also shown that the extended and 3‐star subdivision facets are also equivalent to members of the class of facets with coefficients in {0, 1, 2} for the set covering polytope. Computational results displaying the effectiveness of the facets in a branch‐and‐cut scheme for the maximum planar subgraph problem are presented. © 2007 Wiley Periodicals, Inc. NETWORKS, 2008