Blocks of hypergraphs: applied to hypergraphs and outerplanarity
作者： Ulrik Brandes , Sabine Cornelsen , Barbara Pampel , Arnaud Sallaberry
DOI: 10.1007/978-3-642-19222-7_21
关键词: Graph 、 Discrete mathematics 、 Mathematics 、 Time complexity 、 Vertex connectivity 、 Hypergraph 、 Bipartite graph 、 Hasse diagram 、 Combinatorics 、 Vertex (graph theory)
摘要: A support of a hypergraph H is graph with the same vertex set as in which each hyperedge induces connected subgraph. We show how to test polynomial time whether given has cactus support, i.e. that tree edges and cycles. While it NP-complete decide 2-outerplanar we closed under intersections differences an outerplanar or planar support. In all cases our algorithms yield construction required if exists. The are based on new definition biconnected components hypergraphs.
springer.com
uni-konstanz.de
harvard.edu
archives-ouvertes.fr
springerlink.com参考文章(28)
C. Berge, Graphs and hypergraphs ,(1973)
Stirling Christopher Chow, Generating and drawing area-proportional euler and venn diagrams University of Victoria. ,(2007)
Georg Sander, Layout of Directed Hypergraphs with Orthogonal Hyperedges graph drawing. pp. 381- 386 ,(2003) , 10.1007/978-3-540-24595-7_35
Paul Mutton, Peter Rodgers, Jean Flower, Drawing graphs in Euler diagrams Lecture Notes in Computer Science. pp. 66- 81 ,(2004) , 10.1007/978-3-540-25931-2_9
Anne Verroust, Marie-Luce Viaud, Ensuring the drawability of extended Euler diagrams for up to 8 sets Lecture Notes in Computer Science. pp. 128- 141 ,(2004) , 10.1007/978-3-540-25931-2_13
Michael Kaufmann, Marc van Kreveld, Bettina Speckmann, Subdivision Drawings of Hypergraphs graph drawing. pp. 396- 407 ,(2009) , 10.1007/978-3-642-00219-9_39
Markus Chimani, Carsten Gutwenger, Algorithms for the Hypergraph and the Minor Crossing Number Problems Algorithms and Computation. pp. 184- 195 ,(2007) , 10.1007/978-3-540-77120-3_18
T.R.S Walsh, Hypermaps versus bipartite maps Journal of Combinatorial Theory, Series B. ,vol. 18, pp. 155- 163 ,(1975) , 10.1016/0095-8956(75)90042-8
Marcus Schaefer, Daniel Stefankovic, Decidability of string graphs Proceedings of the thirty-third annual ACM symposium on Theory of computing - STOC '01. ,vol. 68, pp. 241- 246 ,(2001) , 10.1145/380752.380807
John Hopcroft, Robert Tarjan, Efficient Planarity Testing Journal of the ACM. ,vol. 21, pp. 549- 568 ,(1974) , 10.1145/321850.321852