Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Wikipedia says graph theory is used in computer chip design.

... travel, biology, computer chip design, and many other fields. ...

Is there a good reference for that? I can imagine optimal way to draw cpu to chip is to draw shortest hamiltonian cycle in it.

share|cite|improve this question

I'm not sure what would constitute a good reference given the breadth of applications of graph theory in integrated circuit design.

You could glance at the floorplanning, placement and routing chapters of Smith's "Application specific integrated circuits" to get a feel for what is involved. It is an old book (1997) but gives a decent, fairly concise overview.

However, the term 'optimal' is hard to characterize in terms of cpu design, there are many conflicting objectives that need to be addressed. The old adage was "power, speed, area - pick two". Design (in the broad sense) has become considerably more complicated since those relatively simple days.

share|cite|improve this answer
Should "breath" be "breadth"? – Code-Guru Mar 3 '13 at 0:13
Indeed it should, thanks... – copper.hat Mar 3 '13 at 2:54

I don't know about a reference. However, the intuition is that an electrical circuit in a computer chip design is etched into a flat surface. This implies that the graph model of this circuit must be a planar graph. So the theory behind planar graphs is very important in designing such circuits.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.