Saturated simple and k-simple topological graphs

Computational Geometry - Tập 48 - Trang 295-310 - 2015
Jan Kynčl1,2, János Pach2,3, Radoš Radoičić4, Géza Tóth
1Department of Applied Mathematics and Institute for Theoretical Computer Science, Charles University, Faculty of Mathematics and Physics, Malostranské nám. 25, 118 00 Praha 1, Czech Republic
2Alfréd Rényi Institute of Mathematics, Budapest, Hungary
3Ecole Polytechnique Fédérale de Lausanne, Lausanne, Switzerland
4Department of Mathematics, Baruch College, City University of New York, NY, USA

Tài liệu tham khảo

Brass, 2005 Erdős, 1964, A problem in graph theory, Am. Math. Mon., 71, 1107, 10.2307/2311408 Faudree, 2011, A survey of minimum saturated graphs, Electron. J. Comb., 18, DS19 Fulek, 2013, Topological graphs: empty triangles and disjoint matchings, 259 Fox, 2009, Density theorems for bipartite graphs and related Ramsey-type results, Combinatorica, 29, 153, 10.1007/s00493-009-2475-5 P. Hajnal, personal communication. Kynčl, 2013, Improved enumeration of simple topological graphs, Discrete Comput. Geom., 50, 727, 10.1007/s00454-013-9535-8 Kászonyi, 1986, Saturated graphs with minimal number of edges, J. Graph Theory, 10, 203, 10.1002/jgt.3190100209 Levi, 1926, Die Teilung der projektiven Ebene durch Gerade oder Pseudogerade, Ber. Math.-Phys. Kl. Sächs. Akad. Wiss. Leipz., 78, 256 Pach, 2003, Unavoidable configurations in complete topological graphs, Discrete Comput. Geom., 30, 311, 10.1007/s00454-003-0012-9 Pach, 2010, Disjoint edges in topological graphs, J. Comb., 1, 335 A. Ruiz-Vargas, Many disjoint edges in topological graphs, manuscript. Snoeyink, 1991, Sweeping arrangements of curves, vol. 6, 309 Suk, 2013, Disjoint edges in complete topological graphs, Discrete Comput. Geom., 49, 280, 10.1007/s00454-012-9481-x