Michael Hoffmann
Department of Computer Science
ETH Zürich, CAB G33.1
Universitätstrasse 6
CH8092 Zürich
phone  +4144632 73 90 
fax  +4144632 10 63 
email  hoffmann@inf.ethz.ch 
Papers

"TwoPlanar Graphs Are Quasiplanar"
with Csaba D. Tóth.
To appear in Proc. 42nd Internat. Sympos. Math. Found. Comput. Sci. (MFCS '17), Aalborg, Denmark, 2017, 47:147:14.

"Arc diagrams, flip distances, and Hamiltonian triangulations"
with Jean Cardinal, Vincent Kusters, Csaba D. Tóth, and Manuel Wettstein.
To appear in Computational Geometry: Theory and Applications, Volume ?(?), 2017, ?.

"Obedient Plane Drawings for Disk Intersection Graphs" (PDF)
with Bahareh Banyassady, Boris Klemz, Maarten Löffler, and Tillmann Miltzow.
To appear in Proc. 15th Algorithms and Data Struct. Sympos. (WADS '17), Lecture Notes in Computer Science, Volume ?, St. John’s (NF), Canada, 2017, ?.

"Two Computational Geometry Libraries: LEDA and CGAL" (PDF)
with Lutz Kettner and Stefan Näher.
To appear in Handbook of Discrete and Computational Geometry, 2016, ?.

"The Planar Tree Packing Theorem"
with Markus Geyer, Michael Kaufmann, Vincent Kusters, and Csaba D. Tóth.
Appeared in Proc. 32nd Internat. Sympos. Comput. Geom. (SoCG '16), Boston, USA, 2016, 41:141:15.

"Computing Nonsimple Polygons of Minimum Perimeter"
with Sándor P. Fekete, Andreas Haas, Michael Hemmer, Irina Kostitsyna, Dominik Krupke, Florian Maurer, Joseph S. B. Mitchell, Arne Schmidt, Christiane Schmidt, and Julian Troegel.
Appeared in Proc. 15th Sympos. Experimental Algorithms (SEA '16), Lecture Notes in Computer Science, Volume 9685, St. Petersburg, Russia, 2016, 134149.

"An Improved Bound for Orthogeodesic Point Set Embeddings of Trees" (PDF)
with Imre Bárány, Kevin Buchin, and Anita Liebenau.
Appeared in Abstracts 32nd European Workshop on Computational Geometry (EuroCG '16), Lugano, Switzerland, 2016, 4750.

"On Universal Point Sets for Planar Graphs"
with Jean Cardinal and Vincent Kusters.
Appeared in J. Graph Algorithms Appl., Volume 19(1), 2015, 529547.

"Simultaneous Embeddings with Few Bends and Crossings"
with Fabrizio Frati and Vincent Kusters.
Appeared in Proc. 23rd Internat. Sympos. Graph Drawing (GD '15), Lecture Notes in Computer Science, Volume 9411, Los Angeles, USA, 2015, 166179.

"SinglePlayer and TwoPlayer Buttons & Scissors Games"
with Kyle Burke, Erik D. Demaine, Harrison Gregg, Robert A. Hearn, Adam Hesterberg, Hiro Ito, Irina Kostitsyna, Jody Leonard, Maarten Löffler, Aaron Santiago, Christiane Schmidt, Ryuhei Uehara, Yushi Uno, and Aaron Williams.
Appeared in Proc. 18th Japan Conf. Discrete Comput. Geom. Graphs (JCDCGG '15), Lecture Notes in Computer Science, Volume 9943, Kyoto, Japan, 2015, 6072.

"Column Planarity and Partial Simultaneous Geometric Embedding for Outerplanar Graphs" (PDF)
with Luis Barba and Vincent Kusters.
Appeared in Abstracts 31st European Workshop on Computational Geometry (EuroCG '15), Ljubljana, Slovenia, 2015, 5356.

"Arc diagrams, flip distances, and Hamiltonian triangulations"
with Jean Cardinal, Vincent Kusters, Csaba D. Tóth, and Manuel Wettstein.
Appeared in Proc. 32nd Sympos. Theoret. Aspects Comput. Sci. (STACS '15), LIPIcs, Volume 30, München, Germany, 2015, 197210.

"Halving Balls in Deterministic Linear Time"
with Tillmann Miltzow and Vincent Kusters.
Appeared in Proc. 22nd European Sympos. Algorithms (ESA '14), Lecture Notes in Computer Science, Volume 8737, Wroclaw, Poland, 2014, 566578.

"Interference Minimization in Asymmetric Sensor Networks"
with Yves Brise, Kevin Buchin, Dustin Eversmann, and Wolfgang Mulzer.
Appeared in Proc. 10th Internat. Sympos. Algorithms and Experiments for Sensor Systems (ALGOSENSORS '14), Lecture Notes in Computer Science, Volume 8847, Wroclaw, Poland, 2014, 136151.

"Traveltime Maps: Linear Cartograms with Fixed Vertex Locations"
with Kevin Buchin, Arthur van Goethem, Marc van Kreveld, and Bettina Speckmann.
Appeared in Proc. 8th Internat. Conf. Geographic Inform. Sci. (GIScience '14), Lecture Notes in Computer Science, Volume 8728, Vienna, Austria, 2014, 1833.

"Quality Ratios of Measures for Graph Drawing Styles"
with Marc van Kreveld, Vincent Kusters, and Günter Rote.
Appeared in Proc. 26th Canadian Conference on Computational Geometry (CCCG '14), Halifax (NS), Canada, 2014, 3339.

"Graph Drawings with Relative Edge Length Specifications"
with Oswin Aichholzer, Marc van Kreveld, and Günter Rote.
Appeared in Proc. 26th Canadian Conference on Computational Geometry (CCCG '14), Halifax (NS), Canada, 2014, 185191.

"VertexColored Encompassing Graphs"
with Csaba D. Tóth.
Appeared in Graphs Combin., Volume 30(4), 2014, 933947.

"Covering Folded Shapes"
with Oswin Aichholzer, Greg Aloupis, Erik D. Demaine, Martin L. Demaine, Sándor P. Fekete, Anna Lubiw, Jack Snoeyink, and Andrew Winslow.
Appeared in J. Comput. Geom., Volume 5(1), 2014, 150168.

"Separating Balls with a Hyperplane"
with Tillmann Miltzow and Vincent Kusters.
Appeared in Abstracts 30th European Workshop on Computational Geometry (EuroCG '14), EinGedi, Israel, 2014.

"Plane Graphs with Parity Constraints"
with Oswin Aichholzer, Thomas Hackl, Alexander Pilz, Günter Rote, Bettina Speckmann, and Birgit Vogtenhuber.
Appeared in Graphs Combin., Volume 30(1), 2014, 4769.

"Convex Hull Alignment through Translation" (PDF)
with Vincent Kusters, Günter Rote, Maria Saumell, and Rodrigo I. Silveira.
Appeared in Proc. 25th Canadian Conference on Computational Geometry (CCCG '13), Waterloo (ON), Canada, 2013, 295300.

"Covering Folded Shapes" (PDF)
with Oswin Aichholzer, Greg Aloupis, Erik D. Demaine, Martin L. Demaine, Sándor P. Fekete, Anna Lubiw, Jack Snoeyink, and Andrew Winslow.
Appeared in Proc. 25th Canadian Conference on Computational Geometry (CCCG '13), Waterloo (ON), Canada, 2013, 7378.

"Planar Packing of Binary Trees"
with Markus Geyer, Michael Kaufmann, Vincent Kusters, and Csaba D. Tóth.
Appeared in Proc. 13th Algorithms and Data Struct. Sympos. (WADS '13), Lecture Notes in Computer Science, Volume 8037, London (ON), Canada, 2013, 353364.

"Coloring Hypergraphs Induced by Dynamic Point Sets and Bottomless Rectangles"
with Andrei Asinowski, Jean Cardinal, Nathann Cohen, Sébastien Collette, Thomas Hackl, Kolja Knauer, Stefan Langerman, Michał Lasoń, Piotr Micek, Günter Rote, and Torsten Ueckerdt.
Appeared in Proc. 13th Algorithms and Data Struct. Sympos. (WADS '13), Lecture Notes in Computer Science, Volume 8037, London (ON), Canada, 2013, 7384.

"Counting Plane Graphs: Flippability and Its Applications"
with André Schulz, Micha Sharir, Adam Sheffer, Csaba D. Tóth, and Emo Welzl.
Appeared in Thirty Essays on Geometric Graph Theory, 2013, 303325.

"On Universal Point Sets for Planar Graphs"
with Jean Cardinal and Vincent Kusters.
Appeared in Proc. ThailandJapan Joint Conference on Computational Geometry and Graphs (TJJCCGG '12), Lecture Notes in Computer Science, Volume 8296, Bangkok, Thailand, 2013, 3041.

"Maximizing Maximal Angles for Plane Straight Line Graphs"
with Oswin Aichholzer, Thomas Hackl, Clemens Huemer, Attila Pór, Francisco Santos, Bettina Speckmann, and Birgit Vogtenhuber.
Appeared in Computational Geometry: Theory and Applications, Volume 46(1), 2013, 1728.

"Maximum and Minimum against k lies"
with Jiří Matoušek, Yoshio Okamoto, and Philipp Zumstein.
Appeared in Chicago J. Theoretical Computer Science, Volume 2012, 2012, #2.

"Coloring Dynamic Point Sets on a Line"
with Jean Cardinal, Nathann Cohen, Sébastien Collette, Stefan Langerman, and Günter Rote.
Appeared in Abstracts 28th European Workshop on Computational Geometry (EuroCG '12), Assisi, Italy, 2012, 209212.

"Counting Plane Graphs: Flippability and Its Applications"
with Micha Sharir, Adam Sheffer, Csaba D. Tóth, and Emo Welzl.
Appeared in Proc. 12th Algorithms and Data Struct. Sympos. (WADS '11), Lecture Notes in Computer Science, Volume 6844, New York, U.S.A., 2011, 524535.

"Wireless Localization within Orthogonal Polyhedra"
with Tobias Christ.
Appeared in Proc. 23rd Canadian Conference on Computational Geometry (CCCG '11), Toronto (ON), Canada, 2011, 467472.

"The tPebbling Number is Eventually Linear in t"
with Jiří Matoušek, Yoshio Okamoto, and Philipp Zumstein.
Appeared in Electr. J. Combin., Volume 18(1), 2011, #P153.

"Convex Partitions with 2Edge Connected Dual Graphs"
with Marwan Al Jubeh, Mashhood Ishaque, Diane L. Souvaine, and Csaba D. Tóth.
Appeared in Journal of Combinatorial Optimization Volume 22(3), 2011, 409425.

"Maximum and Minimum against k lies"
with Jiří Matoušek, Yoshio Okamoto, and Philipp Zumstein.
Appeared in Proc. 12th Scand. Sympos. Workshops Algorithm Theory (SWAT '10), Lecture Notes in Computer Science, Volume 6139, Bergen, Norway, 2010, 139149.

"Improved Bounds for Wireless Localization"
with Tobias Christ, Yoshio Okamoto, and Takeaki Uno.
Appeared in Algorithmica, Volume 57(3), 2010, 499516.

"Pointed Binary Encompassing Trees: Simple and Optimal"
with Bettina Speckmann and Csaba D. Tóth.
Appeared in Computational Geometry: Theory and Applications, Volume 43(1), 2010, 3541.

"Plane Graphs with Parity Constraints"
with Oswin Aichholzer, Thomas Hackl, Alexander Pilz, Günter Rote, Bettina Speckmann, and Birgit Vogtenhuber.
Appeared in Proc. 11th Algorithms and Data Struct. Sympos. (WADS '09), Lecture Notes in Computer Science, Volume 5664, Banff(AB), Canada, 2009, 1324.

"Wireless Localization with Vertex Guards is NPhard" (PDF)
with Tobias Christ.
Appeared in Proc. 21st Canadian Conference on Computational Geometry (CCCG '09), Vancouver (BC), Canada, 2009, 149152.

"Convex Partitions with 2Edge Connected Dual Graphs"
with Marwan Al Jubeh, Mashhood Ishaque, Diane L. Souvaine, and Csaba D. Tóth.
Appeared in Proc. 15th Ann. Internat. Conf. Computing and Combinatorics (COCOON '09), Lecture Notes in Computer Science, Volume 5609, Niagara Falls (NY), U.S.A., 2009, 192204.

"The Euclidean Degree4 Minimum Spanning Tree Problem is NPhard"
with Andrea Francke.
Appeared in Proc. 25th Annu. Sympos. Comput. Geom. (SoCG '09), Århus, Denmark, 2009, 179188.

"Natural Wireless Localization is NPhard" (PDF)
with Tobias Christ and Yoshio Okamoto.
Appeared in Abstracts 25th European Workshop on Computational Geometry (EuroCG '09), Bruxelles, Belgium, 2009.

"Improved Bounds for Wireless Localization"
with Tobias Christ, Yoshio Okamoto, and Takeaki Uno.
Appeared in Proc. 11th Scand. Workshop Algorithm Theory (SWAT '08), Lecture Notes in Computer Science, Volume 5124, Göteborg, Sweden, 2008, 7789.

"Disjoint Segments have Convex Partitions with 2Edge Connected Dual Graphs" (PDF)
(Gzipped Postscript)
(Postscript)
with Nadia Benbernou, Erik D. Demaine, Martin L. Demaine, Mashhood Ishaque, Diane L. Souvaine, and Csaba D. Tóth.
Appeared in Proc. 19th Canadian Conference on Computational Geometry (CCCG '07), Ottawa, Canada, 2007, 1316.
(Erratum.)

"Maximizing Maximal Angles for Plane Straight Line Graphs"
with Oswin Aichholzer, Thomas Hackl, Clemens Huemer, Attila Pór, Francisco Santos, Bettina Speckmann, and Birgit Vogtenhuber.
Appeared in Proc. 10th Workshop Algorithms Data Struct. (WADS '07), Lecture Notes in Computer Science, Volume 4619, Halifax, Canada, 2007, 458469.

"An Adaptable and Extensible Geometry Kernel"
with Susan Hert, Lutz Kettner, Sylvain Pion, and Michael Seel.
Appeared in Computational Geometry: Theory and Applications, Volume 38(12), 2007, 1636.

"Maximizing Maximal Angles for Plane Straight Line Graphs" (PDF)
with Oswin Aichholzer, Thomas Hackl, Clemens Huemer, Francisco Santos, Bettina Speckmann, and Birgit Vogtenhuber.
Appeared in Abstracts 23rd European Workshop on Computational Geometry (EuroCG '07), Graz, Austria, 2007, 98101.

"The Minimum Weight Triangulation Problem with few Inner Points"
with Yoshio Okamoto.
Appeared in Computational Geometry: Theory and Applications, Volume 34(3), 2006, 149158.

"Coloring Octrees"
with Udo Adamy, József Solymosi, and Miloš Stojaković.
Appeared in Theoretical Computer Science, Volume 363(1), 2006, 1117.

"Spanning Trees across AxisParallel Segments" (PDF)
(Gzipped Postscript)
(Postscript)
with Csaba D. Tóth.
Appeared in Proc. 18th Canadian Conference on Computational Geometry (CCCG '06), Kingston(ON), Canada, 2006, 101104.

"Chordless Paths Through Three Vertices"
with Robert Haas.
Appeared in Theoretical Computer Science, Volume 351(3), 2006, 360371.

"The Traveling Salesman Problem with Few Interior Points"
with Vladimir Deĭneko, Yoshio Okamoto, and Gerhard Woeginger.
Appeared in Oper. Res. Lett., Volume 34(1), 2006, 106110.

"A Simple Linear Algorithm for Computing Rectilinear 3Centers"
Appeared in Computational Geometry: Theory and Applications, Volume 31(3), 2005, 150165.

"Pointed and Colored Binary Encompassing Trees" (PDF)
(Gzipped Postscript)
(Postscript)
with Csaba D. Tóth.
Appeared in Proc. 21st Annu. Sympos. Comput. Geom. (SoCG '05), Pisa, Italy, 2005, 8190.

"Pointed Binary Encompassing Trees: Simple and Optimal" (PDF)
(Gzipped Postscript)
(Postscript)
with Csaba D. Tóth.
Appeared in Abstracts 21st European Workshop on Computational Geometry (EuroCG '05), Eindhoven, Netherlands, 2005, 9396.

"Pointed Binary Encompassing Trees: Simple and Optimal"
with Csaba D. Tóth.
Appeared in Abstracts 14th Annual Fall Workshop Comput. Geom., Cambridge (MA), USA, 2004, 2829.
Invited to a special issue of Computational Geometry: Theory and Applications.

"Chordless Paths Through Three Vertices"
with Robert Haas.
Appeared in Proc. Internat. Workshop on Parameterized and Exact Computation (IWPEC '04), Lecture Notes in Computer Science, Volume 3162, Bergen, Norway, 2004, 2536.

"The Minimum Weight Triangulation Problem with Few Interior Points"
with Yoshio Okamoto.
Appeared in Proc. Internat. Workshop on Parameterized and Exact Computation (IWPEC '04), Lecture Notes in Computer Science, Volume 3162, Bergen, Norway, 2004, 200212.

"The Traveling Salesman Problem with Few Interior Points"
with Vladimir Deĭneko, Yoshio Okamoto, and Gerhard Woeginger.
Appeared in Proc. 10th Ann. Internat. Conf. Computing and Combinatorics (COCOON '04), Lecture Notes in Computer Science, Volume 3106, Jeju Island, Korea, 2004, 268277.

"Coloring Octrees"
with Udo Adamy, József Solymosi, and Miloš Stojaković.
Appeared in Proc. 10th Ann. Internat. Conf. Computing and Combinatorics (COCOON '04), Lecture Notes in Computer Science, Volume 3106, Jeju Island, Korea, 2004, 6271.

"Pointed Binary Encompassing Trees"
with Bettina Speckmann and Csaba D. Tóth.
Appeared in Proc. 9th Scand. Workshop Algorithm Theory (SWAT '04), Lecture Notes in Computer Science, Volume 3111, Humlebæk, Denmark, 2004, 442454.

"PushPushk is PSPACEComplete" (Gzipped Postscript)
(Postscript)
with Erik D. Demaine and Markus Holzer.
Appeared in Proc. 3rd Internat. Conf. Fun with Algorithms (FUN '04), Isola d'Elba, Tuscany, Italy, 2004, 159170.
Preprint.

"New Nomogram for Foetal Weight Estimation based on Hadlock's Twoparameter Formula"
with Giordana M. Beutler, Juozas Kurmanavicius, Emo Welzl, Renate Huch, and Michael Bajka.
Appeared in Ultraschall in der Medizin, Volume 25(1), 2004, 5864.

"Pointed Binary Encompassing Trees" (PDF)
(Gzipped Postscript)
(Postscript)
with Bettina Speckmann and Csaba D. Tóth.
Appeared in Abstracts 20th European Workshop on Computational Geometry (EuroCG '04), Seville, Spain, 2004, 131134.

"Alternating Paths through Disjoint Line Segments"
with Csaba D. Tóth.
Appeared in Information Processing Letters, Volume 87(6), 2003, 287294.

"Degree Bounds for Constrained PseudoTriangulations" (PDF)
(Gzipped Postscript)
(Postscript)
with Oswin Aichholzer, Bettina Speckmann, and Csaba D. Tóth.
Appeared in Proc. 15th Canadian Conference on Computational Geometry (CCCG '03), Halifax(NS), Canada, 2003, 155158.

"Pushing Blocks is Hard"
with Erik D. Demaine, Martin L. Demaine, and Joseph O'Rourke.
Appeared in Computational Geometry: Theory and Applications, Volume 26(1), 2003, 2136.

"Segment Endpoint Visibility Graphs are Hamiltonian"
with Csaba D. Tóth.
Appeared in Computational Geometry: Theory and Applications, Volume 26(1), 2003, 4768.

"Push2F is PSPACEComplete" (PDF)
(Gzipped Postscript)
(Postscript)
with Erik D. Demaine and Robert A. Hearn.
Appeared in Proc. 14th Canadian Conference on Computational Geometry (CCCG '02), Lethbridge(AB), Canada, 2002, 3135.

"Connecting Points in the Presence of Obstacles in the Plane" (PDF)
(Gzipped Postscript)
(Postscript)
with Csaba D. Tóth.
Appeared in Proc. 14th Canadian Conference on Computational Geometry (CCCG '02), Lethbridge(AB), Canada, 2002, 6367.

"Alternating Paths through Disjoint Line Segments" (PDF)
(Gzipped Postscript)
(Postscript)
with Csaba D. Tóth.
Appeared in Abstracts 18th European Workshop on Computational Geometry (EuroCG '02), Warsaw, 2002, 2326.
This is a revised and extended version.

"An Adaptable and Extensible Geometry Kernel" (PDF)
(Gzipped Postscript)
(Postscript)
with Susan Hert, Lutz Kettner, Sylvain Pion, and Michael Seel.
Technical Report, Number 362, Institute for Theoretical Computer Science, ETH Zürich, September, 2001.
Also appeared as MPII20011004 and INRIA RR4270.

"An Adaptable and Extensible Geometry Kernel"
with Susan Hert, Lutz Kettner, Sylvain Pion, and Michael Seel.
Appeared in Proc. 5th Workshop on Algorithm Engineering (WAE '01), Lecture Notes in Computer Science, Volume 2141, Århus, Denmark, August, 2001, 7691.

"Segment Endpoint Visibility Graphs are Hamiltonian" (PDF)
(Gzipped Postscript)
(Postscript)
with Csaba D. Tóth.
Appeared in Proc. 13th Canadian Conference on Computational Geometry (CCCG '01), Waterloo(ON), Canada, 2001, 109112.
Invited to a special issue of Computational Geometry: Theory and Applications.

"Pushing Blocks is NPcomplete for Noncrossing Solution Paths" (PDF)
(Gzipped Postscript)
(Postscript)
with Erik D. Demaine.
Appeared in Proc. 13th Canadian Conference on Computational Geometry (CCCG '01), Waterloo(ON), Canada, 2001, 6568.
Invited to a special issue of Computational Geometry: Theory and Applications.

"Covering Polygons with Few Rectangles" (PDF)
(Gzipped Postscript)
(Postscript)
Appeared in Abstracts 17th European Workshop on Computational Geometry (EuroCG '01), Berlin, 2001, 3942.

"Push
*
is NPhard" (PDF)
(Gzipped Postscript)
(Postscript)
Appeared in Proc. 12th Canadian Conference on Computational Geometry (CCCG '00), Fredericton(NB), Canada, 2000, 205210.

"A Simple Linear Algorithm for Computing Rectangular ThreeCenters" (PDF)
(Gzipped Postscript)
(Postscript)
Appeared in Proc. 11th Canadian Conference on Computational Geometry (CCCG '99), Vancouver(BC), Canada, 1999, 7275.
Invited to a special issue of Computational Geometry: Theory and Applications.
Teaching
Software
Conferences
Program committee member of the
 25th International Symposium on Graph Drawing & Network
Visualization (GD 2017),
Boston, U.S.A. (Sep 25  27, 2017)
 33rd International Symposium on Computational Geometry (SoCG 2017),
Brisbane, Australia (Jul 4 – 7, 2017)
 33rd European Workshop on Computational Geometry (EuroCG
2017), Malmö, Sweden (Apr 5 – Apr 7, 2017)
 25th Multimedia
Exposition in Computational Geometry at the 32nd International
Symposium on Computational Geometry (SoCG 2016), Boston,
U.S.A. (Jun 14 – 18, 2016)
 32nd European Workshop on Computational Geometry (EuroCG 2016), Lugano,
Switzerland (Mar 30 – Apr 1, 2016)
 30th European Workshop on Computational Geometry (EuroCG 2014),
EinGedi, Israel (Mar 3  5, 2014)
 26th Canadian Conference on Computational Geometry (CCCG 2014),
Halifax, Canada (Aug 1113, 2014)
 Young Researchers Forum (YRF)
at the 29th International Symposium on Computational Geometry
(SoCG 2013),
Rio de Janeiro, Brazil (Jun 1720, 2013)
 28th European Workshop on Computational Geometry (EuroCG 2012),
Assisi, Italy (Mar 19  21, 2012)
 16th Annual European Symposium on Algorithms (ESA 2008), Engineering and
Applications Track, Karlsruhe, Germany, (Sep 1519, 2008)
Program committee chair of the
 27th European Workshop on Computational Geometry (EuroCG 2011),
Morschach, Switzerland (Mar 28  30, 2011)
Conference chair of the
 38th International Colloquium on Automata, Languages and
Programming (ICALP
2011) Zürich, Switzerland (Jul 4  8, 2011)
 ALGO 2006,
Zürich, Switzerland (Sep 1115, 2006)