Library

X
feed icon rss

Your email was sent successfully. Check your inbox.

An error occurred while sending the email. Please try again.

Proceed reservation?

Export
  • 1
    Electronic Resource
    Electronic Resource
    Ramsey-Type Results for Geometric Graphs, I (1997)
    Springer
    Discrete & computational geometry 18 (1997), S. 247-255 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract. For any 2-coloring of the ${n \choose 2}$ segments determined by n points in general position in the plane, at least one of the color classes contains a non-self-intersecting spanning tree. Under the same assumptions, we also prove that there exist $\lfloor (n+1)/3 \rfloor$ pairwise disjoint segments of the same color, and this bound is tight. The above theorems were conjectured by Bialostocki and Dierker. Furthermore, improving an earlier result of Larman et al., we construct a family of m segments in the plane, which has no more than $m^{\log 4/\log 27}$ members that are either pairwise disjoint or pairwise crossing. Finally, we discuss some related problems and generalizations.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/PL00009317
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    On Conway's Thrackle Conjecture (1997)
    Springer
    Discrete & computational geometry 18 (1997), S. 369-376 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract. A thrackle is a graph drawn in the plane so that its edges are represented by Jordan arcs and any two distinct arcs either meet at exactly one common vertex or cross at exactly one point interior to both arcs. About 40 years ago, J. H. Conway conjectured that the number of edges of a thrackle cannot exceed the number of its vertices. We show that a thrackle has at most twice as many edges as vertices. Some related problems and generalizations are also considered.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/PL00009322
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    A Generalization of the Erdos - Szekeres Theorem to Disjoint Convex Sets (1998)
    Springer
    Discrete & computational geometry 19 (1998), S. 437-445 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract. Let F denote a family of pairwise disjoint convex sets in the plane. F is said to be in convex position if none of its members is contained in the convex hull of the union of the others. For any fixed k≥ 3 , we estimate P k (n) , the maximum size of a family F with the property that any k members of F are in convex position, but no n are. In particular, for k=3 , we improve the triply exponential upper bound of T. Bisztriczky and G. Fejes Tóth by showing that P 3 (n) 〈 16 n . 〈lsiheader〉 〈onlinepub〉26 June, 1998 〈editor〉Editors-in-Chief: &lsilt;a href=../edboard.html#chiefs&lsigt;Jacob E. Goodman, Richard Pollack&lsilt;/a&lsigt; 〈pdfname〉19n3p437.pdf 〈pdfexist〉yes 〈htmlexist〉no 〈htmlfexist〉no 〈texexist〉yes 〈sectionname〉 〈/lsiheader〉
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/PL00009361
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 4
    Electronic Resource
    Electronic Resource
    New Bounds on Crossing Numbers (2000)
    Springer
    Discrete & computational geometry 24 (2000), S. 623-644 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract. The crossing number , cr(G) , of a graph G is the least number of crossing points in any drawing of G in the plane. Denote by κ(n,e) the minimum of cr(G) taken over all graphs with n vertices and at least e edges. We prove a conjecture of Erdos os and Guy by showing that κ(n,e)n 2 /e 3 tends to a positive constant as n→∈fty and n l e l n 2 . Similar results hold for graph drawings on any other surface of fixed genus. We prove better bounds for graphs satisfying some monotone properties. In particular, we show that if G is a graph with n vertices and e≥ 4n edges, which does not contain a cycle of length four (resp. six ), then its crossing number is at least ce 4 /n 3 (resp. ce 5 /n 4 ), where c〉0 is a suitable constant. These results cannot be improved, apart from the value of the constant. This settles a question of Simonovits.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/s004540010011
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 5
    Electronic Resource
    Electronic Resource
    Extremal Problems for Geometric Hypergraphs (1998)
    Springer
    Discrete & computational geometry 19 (1998), S. 473-484 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract. A geometric hypergraph H is a collection of i -dimensional simplices, called hyperedges or, simply, edges, induced by some (i+1) -tuples of a vertex set V in general position in d -space. The topological structure of geometric graphs, i.e., the case d=2 , i=1 , has been studied extensively, and it proved to be instrumental for the solution of a wide range of problems in combinatorial and computational geometry. They include the k -set problem, proximity questions, bounding the number of incidences between points and lines, designing various efficient graph drawing algorithms, etc. In this paper, we make an attempt to generalize some of these tools to higher dimensions. We will mainly consider extremal problems of the following type. What is the largest number of edges (i -simplices) that a geometric hypergraph of n vertices can have without containing certain forbidden configurations? In particular, we discuss the special cases when the forbidden configurations are k intersecting edges, k pairwise intersecting edges, k crossing edges, k pairwise crossing edges, k edges that can be stabbed by an i -flat, etc. Some of our estimates are tight.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/PL00009365
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 6
    Electronic Resource
    Electronic Resource
    Cutting Glass (2000)
    Springer
    Discrete & computational geometry 24 (2000), S. 481-496 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract. Urrutia asked the following question: Given a family of pairwise disjoint compact convex sets on a sheet of glass, is it true that one can always separate from one another a constant fraction of them using edge-to-edge straight-line cuts? We answer this question in the negative, and establish some lower and upper bounds for the number of separable sets. We also consider the special cases when the family consists of intervals, axis-parallel rectangles, ``fat'' sets, or ``fat'' sets with bounded size.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/s004540010050
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 7
    Electronic Resource
    Electronic Resource
    Canonical Theorems for Convex Sets (1998)
    Springer
    Discrete & computational geometry 19 (1998), S. 427-435 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract. Let F be a family of pairwise disjoint compact convex sets in the plane such that none of them is contained in the convex hull of two others, and let r be a positive integer. We show that F has r disjoint ⌊ c r n⌋ -membered subfamilies F i (1 ≤ i ≤ r) such that no matter how we pick one element F i from each F i , they are in convex position, i.e., every F i appears on the boundary of the convex hull of ⋃ i=1 r F i . (Here c r is a positive constant depending only on r .) This generalizes and sharpens some results of Erdős and Szekeres, Bisztriczky and Fejes Tóth, Bárány and Valtr, and others. 〈lsiheader〉 〈onlinepub〉26 June, 1998 〈editor〉Editors-in-Chief: &lsilt;a href=../edboard.html#chiefs&lsigt;Jacob E. Goodman, Richard Pollack&lsilt;/a&lsigt; 〈pdfname〉19n3p427.pdf 〈pdfexist〉yes 〈htmlexist〉no 〈htmlfexist〉no 〈texexist〉yes 〈sectionname〉 〈/lsiheader〉
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/PL00009360
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 8
    Electronic Resource
    Electronic Resource
    On the Boundary of the Union of Planar Convex Sets (1999)
    Springer
    Discrete & computational geometry 21 (1999), S. 321-328 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract. We give two alternative proofs leading to different generalizations of the following theorem of [1]. Given n convex sets in the plane, such that the boundaries of each pair of sets cross at most twice, then the boundary of their union consists of at most 6n-12 arcs. (An arc is a connected piece of the boundary of one of the sets.) In the generalizations we allow pairs of boundaries to cross more than twice.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/PL00009424
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 9
    Electronic Resource
    Electronic Resource
    Ramsey-Type Results for Geometric Graphs, II (1998)
    Springer
    Discrete & computational geometry 20 (1998), S. 375-388 
    Details
    ISSN: 1432-0444
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract. We show that for any two-coloring of the ${n \choose 2}$ segments determined by n points in the plane, one of the color classes contains noncrossing cycles of lengths $3,4,\ldots,\lfloor\sqrt{n/2}\rfloor$ . This result is tight up to a multiplicative constant. Under the same assumptions, we also prove that there is a noncrossing path of length Ω(n 2/3 ) , all of whose edges are of the same color. In the special case when the n points are in convex position, we find longer monochromatic noncrossing paths, of length $\lfloor({n+1})/{2}\rfloor$ . This bound cannot be improved. We also discuss some related problems and generalizations. In particular, we give sharp estimates for the largest number of disjoint monochromatic triangles that can always be selected from our segments.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/PL00009391
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 10
    Electronic Resource
    Electronic Resource
    Applications of the crossing number (1996)
    Springer
    Algorithmica 16 (1996), S. 111-117 
    Details
    ISSN: 1432-0541
    Keywords: Crossing number ; Geometric graph ; Bisection width ; Triangulation
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract LetG be a graph ofn vertices that can be drawn in the plane by straight-line segments so that nok+1 of them are pairwise crossing. We show thatG has at mostc k nlog2k−2 n edges. This gives a partial answer to a dual version of a well-known problem of Avital-Hanani, Erdós, Kupitz, Perles, and others. We also construct two point sets {p 1,⋯,p n }, {q 1,⋯,q n } in the plane such that any piecewise linear one-to-one mappingf∶R 2→R 2 withf(pi)=qi (1≤i≤n) is composed of at least Ω(n 2) linear pieces. It follows from a recent result of Souvaine and Wenger that this bound is asymptotically tight. Both proofs are based on a relation between the crossing number and the bisection width of a graph.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02086610
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...