<p>Some missing topics from <a href="http://en.wikipedia.org/wiki/Book%3aGraph_Algorithms">my collection of graph algorithms articles</a>:</p>

<ul>
<li>Dynamic graph algorithms</li>
<li>K shortest paths</li>
<li>Spanners and approximate shortest path data structures</li>
</ul>

<p>Also, not so much missing topics, but a lot of the articles on topics covered by undergraduate algorithms classes kind of look like they were written by students in those classes. There's a deeper level of understanding missing, and they take a dogmatic point of view that reflects a single textbook rather than a synthesis of multiple sources. More expert help there could be useful.</p>

CC BY-SA 3.0
2011-09-08T05:04:55.830Z
I didn't know you could make books like that with wikipedia! That is really awesome!
Artem Kaznatcheev
CC BY-SA 3.0
2011-09-08T09:09:20.287Z
Thanks for all your hard work in making this part of Wikipedia the most convenient online resource for graph theory.
András Salamon
CC BY-SA 3.0
2011-09-07T20:43:00.593Z
2011-09-07T20:43:00.593Z
David Eppstein
<p>I would <em>love</em> a Wikipedia page on the Abstract Tile Assembly Model.</p>

CC BY-SA 3.0
2011-09-07T20:54:13.690Z
2011-09-07T20:54:13.690Z
Aaron Sterling
<p>The entry on the <a href="http://en.wikipedia.org/wiki/Johnson%E2%80%93Lindenstrauss_lemma" rel="nofollow">Johnson-Lindenstrauss Lemma</a> lacks a complete set of references, and might also benefit from a high level explanation of the different types of algorithms available. </p>

CC BY-SA 3.0
2011-09-07T21:51:08.407Z
2011-09-07T21:51:08.407Z
Suresh Venkat
<p>The current article on <a href="http://en.wikipedia.org/wiki/Computational_topology" rel="nofollow">computational topology</a> covers only one small (but important!) subfield.  Other subfields are covered in <a href="http://en.wikipedia.org/wiki/Topological_data_analysis" rel="nofollow">topological data analysis</a>, <a href="http://en.wikipedia.org/wiki/Topological_graph_theory" rel="nofollow">topological graph theory</a>, <a href="http://en.wikipedia.org/wiki/Discrete_exterior_calculus" rel="nofollow">discrete exterior calculus</a>, and possibly even <a href="http://en.wikipedia.org/wiki/Topological_Quantum_Computing" rel="nofollow">topological quantum computing</a>.  But even combined, the resulting article would be incomplete.</p>

<p>Yes, yes, I know.</p>

CC BY-SA 3.0
2011-09-09T07:45:34.313Z
2011-09-09T07:45:34.313Z
Jeffε
<p>Which missing TCS topics on Wikipedia would you most like there to be an article about?</p>

<p>They could be glaring omissions or just topics you think should really have an article.</p>

<p>One topic per answer please so that the most wanted ones can be voted up.</p>

<p><strong>Update 5/2/2017</strong>: Shuchi Chawla is leading an effort to <a href="https://thmatters.wordpress.com/2017/05/02/tcs-wikipedia-project/" rel="noreferrer">improve TCS coverage on wikipedia</a>. I'm adding this update in the hopes that people will update their answers as appropriate, add more answers, and/or contribute to the effort!</p>

CC BY-SA 3.0
2011-09-07T20:36:38.883Z
If you don't restrict the possible topics to TCS related, then this question is off topic.
Tyson Williams
CC BY-SA 3.0
2011-09-07T20:39:55.073Z
And even then, I would still think this is off topic.
Lev Reyzin
CC BY-SA 3.0
2011-09-07T20:42:46.643Z
@Tyson Williams: The question is now edited to explicitly ask for TCS topics.
WSSW
CC BY-SA 3.0
2011-09-07T20:45:52.120Z
@WSSW Do you have a Wikipedia account?
Tyson Williams
CC BY-SA 3.0
2011-09-07T20:59:49.003Z
I think it could be ok if it gives a list of topics for people to work on.
Suresh Venkat
CC BY-SA 3.0
2011-09-07T21:19:44.697Z
*Why* are you asking? What do you plan to do with the answer?
Jukka Suomela
CC BY-SA 3.0
2011-09-08T01:51:26.610Z
I think this can be OK, something similar to these MO question: [Books you would like to read (if somebody would just write them...)](https://mathoverflow.net/questions/53036/books-you-would-like-to-read-if-somebody-would-just-write-them) or [A Book You Would Like to Write](https://mathoverflow.net/questions/54232/a-book-you-would-like-to-write)
Kaveh
CC BY-SA 3.0
2011-09-08T04:37:24.200Z
interaction with wikipedia is always nice. Note that we are starting to show up as a [source in wikipedia](http://en.wikipedia.org/w/index.php?title=Special%3ASearch&redirs=1&search=cstheory.stackexchange&fulltext=Search&ns0=1).
Artem Kaznatcheev
CC BY-SA 3.0
2011-09-08T04:40:27.287Z
@Kaveh one possible issue: this same exact question (with the obvious minor changes) was also asked (and closed!) on [math.SE](http://math.stackexchange.com/q/62666/13668) and [physics.SE](http://physics.stackexchange.com/q/14439).
Artem Kaznatcheev
CC BY-SA 3.0
2011-09-08T05:32:28.540Z
@Artem, thanks, I checked them. I agree that this is not the best way of using the site, but I think it is OK. (I don't think we are ranking anything here nor polling, and the fact that there is also a Wikipedia page for articles that should be written doesn't mean we should not ask what is missing from the list there. In any case, if anyone wants to continue discussing the question please it is better to start a meta discussion.)
Kaveh
CC BY-SA 3.0
2011-09-09T16:19:04.877Z
@Artem that's neat: along with our generally high google rank, these are good signs.
Suresh Venkat
CC BY-SA 3.0
2017-05-03T17:36:03.967Z
It isn't missing, but the PCP Theorem article is rather scant and could use a lot of elaboration and context to explain why it is so important. The section on hardness of approximation fails to explain the connection between "traditional" PCP and hardness of approximation, and would be greatly improved by an example showing how to use PCP to prove a hardness of approximation result. There is a hardness of approximation page, but it too is severely lacking in details and examples: https://en.wikipedia.org/wiki/PCP_theorem https://en.wikipedia.org/wiki/Hardness_of_approximation
Stella Biderman
<soft-question><big-list><survey>
Missing Wikipedia articles
WSSW
# Missing Wikipedia articles

(Asked by: username_0 on 2011-09-07)

Which missing TCS topics on Wikipedia would you most like there to be an article about?

They could be glaring omissions or just topics you think should really have an article.

One topic per answer please so that the most wanted ones can be voted up.

**Update 5/2/2017**: Shuchi Chawla is leading an effort to [improve TCS coverage on wikipedia](https://thmatters.wordpress.com/2017/05/02/tcs-wikipedia-project/). I'm adding this update in the hopes that people will update their answers as appropriate, add more answers, and/or contribute to the effort!

**Tags:** soft-question, big-list, survey
> **Comments:**
> **username_1**: If you don't restrict the possible topics to TCS related, then this question is off topic.  
> **username_2**: And even then, I would still think this is off topic.  
> **username_0**: @Tyson Williams: The question is now edited to explicitly ask for TCS topics.  
> **username_1**: @WSSW Do you have a Wikipedia account?  
> **username_3**: I think it could be ok if it gives a list of topics for people to work on.  
> **username_4**: *Why* are you asking? What do you plan to do with the answer?  
> **username_5**: I think this can be OK, something similar to these MO question: [Books you would like to read (if somebody would just write them...)](https://mathoverflow.net/questions/53036/books-you-would-like-to-read-if-somebody-would-just-write-them) or [A Book You Would Like to Write](https://mathoverflow.net/questions/54232/a-book-you-would-like-to-write)  
> **username_6**: interaction with wikipedia is always nice. Note that we are starting to show up as a [source in wikipedia](http://en.wikipedia.org/w/index.php?title=Special%3ASearch&redirs=1&search=cstheory.stackexchange&fulltext=Search&ns0=1).  
> **username_6**: @Kaveh one possible issue: this same exact question (with the obvious minor changes) was also asked (and closed!) on [math.SE](http://math.stackexchange.com/q/62666/13668) and [physics.SE](http://physics.stackexchange.com/q/14439).  
> **username_5**: @Artem, thanks, I checked them. I agree that this is not the best way of using the site, but I think it is OK. (I don't think we are ranking anything here nor polling, and the fact that there is also a Wikipedia page for articles that should be written doesn't mean we should not ask what is missing from the list there. In any case, if anyone wants to continue discussing the question please it is better to start a meta discussion.)  
> **username_3**: @Artem that's neat: along with our generally high google rank, these are good signs.  
> **username_7**: It isn't missing, but the PCP Theorem article is rather scant and could use a lot of elaboration and context to explain why it is so important. The section on hardness of approximation fails to explain the connection between "traditional" PCP and hardness of approximation, and would be greatly improved by an example showing how to use PCP to prove a hardness of approximation result. There is a hardness of approximation page, but it too is severely lacking in details and examples: https://en.wikipedia.org/wiki/PCP_theorem https://en.wikipedia.org/wiki/Hardness_of_approximation  

---

## 4 answers

### Answer by username_8 on 2011-09-07. Score: 22

Some missing topics from [my collection of graph algorithms articles](http://en.wikipedia.org/wiki/Book%3aGraph_Algorithms):

* Dynamic graph algorithms
* K shortest paths
* Spanners and approximate shortest path data structures

Also, not so much missing topics, but a lot of the articles on topics covered by undergraduate algorithms classes kind of look like they were written by students in those classes. There's a deeper level of understanding missing, and they take a dogmatic point of view that reflects a single textbook rather than a synthesis of multiple sources. More expert help there could be useful.

> **Comments:**
> **username_6**: I didn't know you could make books like that with wikipedia! That is really awesome!  
> **username_9**: Thanks for all your hard work in making this part of Wikipedia the most convenient online resource for graph theory.  

---

### Answer by username_10 on 2011-09-07. Score: 6

I would *love* a Wikipedia page on the Abstract Tile Assembly Model.


---

### Answer by username_3 on 2011-09-07. Score: 4

The entry on the [Johnson-Lindenstrauss Lemma](http://en.wikipedia.org/wiki/Johnson%E2%80%93Lindenstrauss_lemma) lacks a complete set of references, and might also benefit from a high level explanation of the different types of algorithms available.


---

### Answer by username_11 on 2011-09-09. Score: 4

The current article on [computational topology](http://en.wikipedia.org/wiki/Computational_topology) covers only one small (but important!) subfield. Other subfields are covered in [topological data analysis](http://en.wikipedia.org/wiki/Topological_data_analysis), [topological graph theory](http://en.wikipedia.org/wiki/Topological_graph_theory), [discrete exterior calculus](http://en.wikipedia.org/wiki/Discrete_exterior_calculus), and possibly even [topological quantum computing](http://en.wikipedia.org/wiki/Topological_Quantum_Computing). But even combined, the resulting article would be incomplete.

Yes, yes, I know.


---

