BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260408T205255Z
UID:Seminar-dept-1286@lxserverA.csc.liv.ac.uk.csc.liv.ac.uk
ORGANIZER:CN=Lutz Oettershagen:MAILTO:Lutz.Oettershagen@liverpool.ac.uk
DTSTART:20250908T090000
DTEND:20250908T100000
SUMMARY:School Seminar Series
DESCRIPTION:Janos Pach: [MACSMIN] Mysteries about crossing numbers\n\nFor any graph G, the crossing number cr(G) of G is defined as the smallest number k such that G can be drawn in the plane with k crossing points between its edges. The pairwise crossing number pair-cr(G) of G is defined in a similar way, except that in this case we want to minimize the number of crossing pairs of edges. Obviously, pair-cr(G) is at most cr(G). It is one of the most annoying unsolved problems for graph embeddings whether there exists a graph for which these two parameters do not coincide. Since computing these parameters are NP-complete problems, it is difficult to test the inequality even for small graphs. After giving a whirlwind survey of the topic, we discuss some recent develop. \n\n\n\nThis talk is not a standard seminar talk and is part of the MACSMIN workshop (https://kurlin.org/macsmin/2025.php). \n\nAdvertised at the request of Vitaliy Kurlin  \n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=1286
LOCATION:Materials Innovation Factory, Liverpool, UK
END:VEVENT
END:VCALENDAR