Name: Dr. Markus CHIMANI
University Data: Chair of Algorithm Engineering
Computer Science Department
TU Dortmund
eMail: markus . chimani * tu - dortmund . de
Phone: (+49)(231) 755-7706
Fax: (+49)(231) 755-7740
Room: 237
Address: Otto-Hahn-Str. 14
44227 Dortmund
Germany
>>> JENA
Since April 1st (2010), I'm juniorprofessor for Algorithm Engineering at the Friedrich-Schiller-University Jena:
Please visit the my current page, instead of this one:
www.ae.uni-jena.de
.










Everything below is outdated!










Really, there is nothing more to see here...









Everything below only remains here for historical reasons!









Useful Stuff
OGDF - Open Graph Drawing Framework
Conferences (Carsten's page)
Solving the k-Cardinality Tree Problem to provable optimality using a cut-based ILP (Maria's page)
Useful Teaching Stuff
German: Hinweise zur Foliengestaltung - download PDF

Current Teaching
VO+UE Graphenalgorithmen WS09
Past Teaching
PG (534) Vehicle Routing WS08/09 + SS09
Seminar Algorithm Engineering SS09
Proseminar Algorithmen und Datenstrukturen WS08/09
Seminar Flüsse in Netzwerken SS08
PG (517) Evakuierungsprobleme WS07/08 + SS08
Seminar Algorithm Engineering WS07/08
PG (503) Xaver: Algorithm Engineering XXL WS06/07 + SS07
Übung Datenstrukturen, Algorithmen und Programmierung 2 SS06
Proseminar Graphentheorie SS06
PG (478) OGDF: An Open Graph Drawing Framework WS05/06 + SS06
Übung Algorithm Engineering WS05/06
Seminar Netzwerk-Design Algorithmen WS05/06
Übung Datenstrukturen, Algorithmen und Programmierung 2 SS05
Seminar Automatisches Zeichnen von Graphen WS04/05
Proseminar Algorithmen der Bioinformatik WS04/05
Supervised Theses
Dipl. Th. HUGO -
Dipl. Th. Exact Circular Crossing Minimization Apr. 2009
Dipl. Th. Kuratowski Extraction Mar. 2007
Dipl. Th. Evolutionary Crossing Minimization Jan. 2006

Research Interests
Algorithm Engineering
Exact Solutions for NP-hard problems
(Computation of) Crossing number and other non-planarity measures; Graph Drawing; Graph Theory
Network Optimization
ILP, Branch-and-Cut, Column Generation
Combinatorial Optimization
Technical Reports
M. Chimani, M. Kandyba, M. Maren.
2-InterConnected Facility Location: Specifications, Complexity Results, and Exact Solutions
Technical Report TR09-1-008. Chair XI Algorithm Engineering, TU Dortmund. December 2009.
Refereed Conference Papers
The downloadable PDFs of the papers below are all either technical reports or preprints, which differ from the published papers.
2010
P. Hliněný, M. Chimani.
Approximating the Crossing Number of Graphs Embeddable in Any Orientable Surface
ACM-SIAM Symposium on Discrete Algorithms 2010, Austin, Texas (SODA10), to appear.
2009
M. Chimani, C. Gutwenger, P. Mutzel, H.-M. Wong.
Upward Planarization Layout
17th International Symposium on Graph Drawing 2009, Chicago (GD09), to appear in LNCS.
M. Chimani, C. Gutwenger, P. Mutzel, C. Wolf
Inserting a Vertex into a Planar Graph
ACM-SIAM Symposium on Discrete Algorithms 2009, New York (SODA09), pp. 375-383, ACM Press, 2009. (link to original)
2008
M. Chimani, C. Gutwenger, M. Jansen, K. Klein, P. Mutzel
Computing Maximum C-Planar Subgraphs
16th International Symposium on Graph Drawing 2008, Heraklion (GD08), LNCS 5417, pp. 114-120, Springer, 2009.
M. Chimani, P. Mutzel, I. Bomze
A New Approach to Exact Crossing Minimization
16th Annual European Symposium on Algorithms 2008, Karlsruhe (ESA08), LNCS 5193, pp. 284-296, Springer, 2008.
M. Chimani, M. Kandyba, I. Ljubic, P. Mutzel.
Strong Formulations for the 2-Node-Connected Steiner Network Problems
2nd Annual International Conference on Combinatorial Optimization and Applications 2008, St. John's, Newfoundland (COCOA08), LNCS 5165, pp. 190-200, Springer, 2008.
Tech.Report: TR07-1-008, November 2007
M. Chimani, C. Gutwenger, P. Mutzel, H.-M. Wong.
Layer-Free Upward Crossing Minimization
7th International Workshop on Experimental Algorithms 2008, Cape Cod (WEA08), LNCS 5038, pp. 55-68, Springer, 2008.
M. Chimani, M. Jünger, M. Schulz.
Crossing Minimization meets Simultaneous Drawing
2008 IEEE Pacific Visualization Symposium, Kyoto (PacificVis08), pp. 33-40.
M. Chimani, M. Kandyba, I. Ljubic, P. Mutzel.
Obtaining Optimal k-Cardinality Trees Fast
10th Workshop on Algorithm Engineering & Experiments 2008, San Francisco (ALENEX08), SIAM, pp. 27-36.
2007
M. Chimani, C. Gutwenger.
Algorithms for the Hypergraph and the Minor Crossing Number Problems
18th Annual International Symposium on Algorithms and Computation 2007, Sendai (ISAAC07), LNCS 4835, pp. 184-195, Springer, 2007.
M. Chimani, P. Mutzel, J.M. Schmidt.
Efficient Extraction of Multiple Kuratowski Subdivisions
15th International Symposium on Graph Drawing 2007, Sydney (GD07), LNCS 4875, pp. 159-170, Springer, 2007.
Tech.Report: TR07-1-002, June 2007
M. Chimani, M. Kandyba, M. Preuss.
Hybrid Numerical Optimization for Combinatorial Network Problems
4th International Workshop on Hybrid Metaheuristics 2007, Dortmund (HM07), LNCS 4771, pp. 185-200, Springer, 2007.
M. Chimani, M. Kandyba, P. Mutzel.
A New ILP Formulation for 2-Root-Connected Prize-Collecting Steiner Networks
15th Annual European Symposium on Algorithms 2007, Eilat (ESA07), LNCS 4698, pp. 681-692, Springer, 2007.
Tech.Report: TR07-1-001, April 2007
2006
M. Chimani, C. Gutwenger, P. Mutzel.
Experiments on Exact Crossing Minimization using Column Generation
5th International Workshop on Experimental Algorithms 2006, Menorca (WEA06), LNCS 4007, pp. 303-315, Springer, 2006.
C. Gutwenger, M. Chimani.
Non-Planar Core Reduction of Graphs
13th International Symposium on Graph Drawing 2005, Limerick (GD05), LNCS 3843, pp. 223-234, Springer, 2006.
2005
C. Rich, C. Sidner, N. Lesh, A. Garland, S. Booth, M. Chimani.
DiamondHelp: A Collaborative Interface Framework for Networked Home Appliances
IEEE International Conference on Distributed Computing Systems Workshops (ICDCS 2005) / 5th International WorkShop on Smart Appliances and Wearable Computing 2005 (IWSAWC), pp. 514-519, IEEE Computer Society Press, 2005.
M. Chimani, N. Lesh, M. Mitzenmacher, C. Sidner, H. Tanaka.
A Case Study in Large-Scale Interactive Optimization
International Conference on Artificial Intelligence and Applications 2005 (AIA05), IASTED-Proc., pp.24-29, Acta Press, Anaheim CA, 2005.
M. Chimani, G.W. Klau, R. Weiskircher.
Non-Planar Orthogonal Drawings with Fixed Topology
SOFSEM 2005: Theory and Practice of Computer Science, Liptovsky Jan, LNCS 3381, pp.96-105, Springer, 2005.
Journal Articles
M. Chimani, C. Gutwenger, P. Mutzel, H.-M. Wong.
Layer-Free Upward Crossing Minimization
ACM Journal of Experimental Algorithmics (accepted)
M. Chimani, M. Kandyba, I. Ljubic, P. Mutzel.
Oriented-based Models for {0,1,2}-Survivable Network Design: Theory and Practice
Mathematical Programming, Series B (accepted)
M. Chimani, C. Gutwenger, P. Mutzel.
Experiments on Exact Crossing Minimization using Column Generation
ACM Journal of Experimental Algorithmics, Vol. 14(3), pp. 4.1-4.18, 2009
M. Chimani, M. Kandyba, I. Ljubic, P. Mutzel.
Obtaining Optimal k-Cardinality Trees Fast
ACM Journal of Experimental Algorithmics, Vol. 14(2), pp. 5.1-5.23, 2009
M. Chimani, C. Gutwenger.
Non-Planar Core Reduction of Graphs
Discrete Mathematics, Vol. 309(7), pp. 1838-1855, 2009
C. Buchheim, M. Chimani, D. Ebner, C. Gutwenger, M. Jünger, G.W. Klau, P. Mutzel, R. Weiskircher.
A Branch-and-Cut Approach to the Crossing Number Problem
Discrete Optimization, Vol. 5(2), Special Issue in Memory of George B. Dantzig, pp. 373-388, 2008
M. Chimani, C. Gutwenger, P. Mutzel.
On the Minimum Cut of Planarizations
Electronic Notes in Discrete Mathematics, Vol. 28, pp. 177-184, 2007.
C. Rich, C. Sidner, N. Lesh, A. Garland, S. Booth, M. Chimani.
DiamondHelp: A New Interaction Design for Networked Home Appliances
Personal and Ubiquitous Computing, Vol. 10(2), pp.187-190, Springer, 2006.
Posters & System Demos
M. Chimani, P. Hliněný, P. Mutzel.
Approximating the Crossing Number of Apex Graphs
16th International Symposium on Graph Drawing 2008, Heraklion (GD08), LNCS 5417, pp. 432-434, Springer, 2009
M. Chimani, C. Gutwenger, M. Jünger, K. Klein, P. Mutzel, M. Schulz.
The Open Graph Drawing Framework
15th International Symposium on Graph Drawing 2007, Sydney (GD07)
C. Rich, C. Sidner, N. Lesh, A. Garland, S. Booth, M. Chimani.
DiamondHelp: A New Interaction Design for Networked Home Appliances
Third International Conference on Appliance Design 2005 (3AD), Finalist of Design Competition
C. Rich, C. Sidner, N. Lesh, A. Garland, S. Booth, M. Chimani.
DiamondHelp: A Collaborative Task Guidance Framework for Complex Devices
20th National Conference on Artificial Intelligence; Intelligent Systems Demonstrations (AAAI 2005), pp.1700-1701, 2005
Book Chapters and Lecture Notes
M. Chimani and K. Klein.
Algorithm Engineering: Concepts and Practice
Chapter in: Experimental Methods for the Analysis of Optimization Algorithms.
T. Bartz-Beielstein, M. Chiarandini, L. Paquete, M. Preuss, Eds., Springer 2010.
M. Chimani.
Computing Crossing Numbers
Chapter in: Ausgezeichnete Informatikdissertationen 2008.
Dorothea Wagner et al., Eds. GI-Edition LNI Dissertations 9, pp. 41-50, Gesellschaft für Informatik (in German, 2009)
P. Mutzel, M. Chimani, C. Gutwenger, K. Klein.
Datenstrukturen, Algorithmen und Programmieren 2
Lecture Notes/Vorlesungsskript, TU Dortmund, since 2005 (in German, link to version 2009)
Theses
Computing Crossing Numbers
PhD Thesis, Technical University Dortmund, 2008
Bend-Minimal Orthogonal Drawing of Non-Planar Graphs
Diploma Thesis, Vienna University of Technology, 2004
--- End of Page ---