TY - GEN A1 - Hougardy, Stefan A1 - Lutz, Frank H. A1 - Zelke, Mariano T1 - Polyhedra of Genus 2 with 10 Vertices and Minimal Coordinates N2 - We give coordinate-minimal geometric realizations in general position of all 865 vertex-minimal triangulations of the orientable surface of genus 2 in the 4x4x4-cube. T3 - ZIB-Report - 06-12 KW - triangulated surfaces KW - minimal triangulations KW - polyhedral realizations Y1 - 2006 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9054 ER - TY - GEN A1 - Hougardy, Stefan A1 - Lutz, Frank H. A1 - Zelke, Mariano T1 - Polyhedra of Genus 3 with 10 Vertices and Minimal Coordinates N2 - We give coordinate-minimal geometric realizations in general position for 17 of the 20 vertex-minimal triangulations of the orientable surface of genus 3 in the 5x5x5-cube. T3 - ZIB-Report - 06-13 KW - triangulated surfaces KW - minimal triangulations KW - polyhedral realizations Y1 - 2006 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9064 ER - TY - GEN A1 - Hougardy, Stefan A1 - Wagler, Annegret T1 - Perfectness is an Elusive Graph Property N2 - A graph property is called elusive (or evasive) if every algorithm for testing this property has to read in the worst case $n\choose 2$ entries of the adjacency matrix of the given graph. Several graph properties have been shown to be elusive, e.g. planarity (Best et al) or $k$-colorability (Bollobas). A famous conjecture of Karp says that every non-trivial monotone graph property is elusive. We prove that a non-monotone but hereditary graph property is elusive: perfectness. T3 - ZIB-Report - 02-11 KW - perfect graph KW - elusive graph property Y1 - 2002 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6787 ER -